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:

  1. 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.
  2. If only selecting “k” elements, the diagonals only need to be sorted up until diagonals containing at least “k” elements have been sorted.
  3. It’s possible to parallelize building the other end of the array.
  4. There exists an algorithm which can perform the initial sort in n * log(sqrt(n)) time which would make this similar speed to quicksort.
One clap, two clap, three clap, forty?

By clapping more or less, you can signal to us which stories really stand out.