# An Efficient Selection Sort

Selection Sort is generally considered O(n²) time complexity, but I provide an implementation below which can generally be considered to be O(n log(n)) time complexity for data which has n elements.

It functions based on the fact that if we sort every row and column in a matrix, every element will be greater than or equal to elements to the right and below it. If we sort on diagonals, this property will be retained, and elements will be greater than others which fall underneath the diagonal it is on.

The shape of the matrix is irrelevant.

# assuming mx is square, return an array with the diagonals of the matrix

def diagonals(mx)

result = []

amt = mx.length

amt.times do |x|

diag = []

start = x

until x == -1 do

diag << (mx[start-x][x])

x = x-1

end

result.push diag

end

amt.pred.times do |x|

diag = []

start = x

until x == -1 do

diag.push(mx[amt-1-x][amt-1-(start-x)])

x = x-1

end

result.push diag

end

result

end

# convert the result from above back into a square matrix

def diagonals_to_a(diags)

len = (diags.length.next) >> 1

result = ([nil]*len*len).each_slice(len).map { |x| x }

flat_diags = diags.flatten(1)

c = 0

len.times do |x|

start = x

until x == -1 do

result[start-x][x] = flat_diags[c]

x -= 1

c += 1

end

end

len.pred.times do |x|

start = x

until x == -1 do

result[len-1-x][len-1-(start-x)] = flat_diags[c]

x -= 1

c += 1

end

end

result

end

def min(a, b)

b > a ? a : b;

end

# sorting algorithm using matrices

def matrix_select_sort(arr)

len = Math.sqrt(arr.length).floor

container = arr

.each_slice(len)

.map(&:sort)

.transpose

.map(&:sort)

container = diagonals(container)

.map(&:sort)

container = diagonals_to_a(container)

check_bounds = (0..2)

result = []

selected = check_bounds.begin

until check_bounds.begin == len -1 do

selected = check_bounds.begin

check_bounds.each do |n|

if container[selected].first > container[n].first

(selected = n) == check_bounds.end && check_bounds = (check_bounds.begin..min(check_bounds.end, len-1))

end

end

result.push(container[selected].shift)

container[check_bounds.begin].length == 0 && check_bounds = (check_bounds.begin.next..check_bounds.end)

end

result + container.last

end

vals = (1..(900 * 900)).to_a.shuffle

start = Time.now

matrix_select_sort(vals)

p "matrix select", Time.now - start

startNativeSort = Time.now

vals.sort

p "native", Time.now - startNativeSort

Conjectures:

- This is specifically 4 * n log(n) time complexity, as can be seen from testing compared to ruby’s native sorting algorithm which is n log(n) time complexity.
- If only selecting “k” elements, the diagonals only need to be sorted up until diagonals containing at least “k” elements have been sorted.
- It’s possible to parallelize building the other end of the array.
- There exists an algorithm which can perform the initial sort in n * log(sqrt(n)) time which would make this similar speed to quicksort.