Slowsort in Ruby

Overview

Slowsort is another unserious sorting algorithm first published in 1986 by Andrei Broder and Jorge Stolfi in their paper Pessimal Algorithms and Simplexity Analysis. First it sorts the first half of the array recursively, then the second half of the array recursively, then it places the highest element of the array at the end and recursively sorts the rest of the list.

Concise

def slowsort(a, s, f)
  return a if s >= f
  p a

  m = ((s + f) / 2).floor
  slowsort(a, s, m)
  slowsort(a, m+1, f)

  if a[f] < a[m]
    a[f], a[m] = a[m], a[f]
  end

  slowsort(a, s, f-1)
end

u = (0..9).to_a.sort{ rand() - 0.5 }[0..7]
p u

s = slowsort(u, 0, u.length-1)
p s
slowsort.rb

Verbose

# Slowsort
#
# Input: A sequence of numbers in any order.
# Output: An ordered sequence from smallest number to largest.
#
def slowsort(numbers, start, finish)

  # Return when the start and finish are the same.
  return numbers if start >= finish
  p numbers

  # Calculate middle.
  middle = ((start + finish) / 2).floor

  # Recursively slowsort the first and second halves.
  slowsort(numbers, start, middle)
  slowsort(numbers, middle+1, finish)

  # If the last number is a lower number than the middle, swap.
  if numbers[finish] < numbers[middle]
    numbers[finish], numbers[middle] = numbers[middle], numbers[finish]
  end

  # Recursively slowsort the rest of the list without the final sorted element.
  slowsort(numbers, start, finish-1)
end

# Generate array of ten random integers.
unsorted = (0..9).to_a.sort{ rand() - 0.5 }[0..7]
puts unsorted.inspect

# Sort.
sorted = slowsort(unsorted, 0, unsorted.length-1)
puts sorted.inspect
slowsort_verbose.rb

Sample Input and Output

$ ruby slowsort_verbose.rb
[0, 3, 9, 7, 6, 5, 8, 4]
[0, 3, 9, 7, 6, 5, 8, 4]
[0, 3, 9, 7, 6, 5, 8, 4]
[0, 3, 9, 7, 6, 5, 8, 4]
[0, 3, 9, 7, 6, 5, 8, 4]
[0, 3, 7, 9, 6, 5, 8, 4]
[0, 3, 7, 9, 6, 5, 8, 4]
[0, 3, 7, 9, 6, 5, 8, 4]
[0, 3, 7, 9, 6, 5, 8, 4]
[0, 3, 7, 9, 6, 5, 8, 4]
[0, 3, 7, 9, 5, 6, 8, 4]
[0, 3, 7, 9, 5, 6, 4, 8]
[0, 3, 7, 9, 5, 6, 4, 8]
[0, 3, 7, 9, 5, 4, 6, 8]
[0, 3, 7, 8, 4, 5, 6, 9]
[0, 3, 7, 8, 4, 5, 6, 9]
[0, 3, 7, 8, 4, 5, 6, 9]
[0, 3, 7, 8, 4, 5, 6, 9]
[0, 3, 7, 8, 4, 5, 6, 9]
[0, 3, 7, 8, 4, 5, 6, 9]
[0, 3, 7, 8, 4, 5, 6, 9]
[0, 3, 7, 8, 4, 5, 6, 9]
[0, 3, 7, 8, 4, 5, 6, 9]
[0, 3, 7, 8, 4, 5, 6, 9]
[0, 3, 7, 6, 4, 5, 8, 9]
[0, 3, 7, 6, 4, 5, 8, 9]
[0, 3, 7, 6, 4, 5, 8, 9]
[0, 3, 7, 6, 4, 5, 8, 9]
[0, 3, 7, 6, 4, 5, 8, 9]
[0, 3, 7, 6, 4, 5, 8, 9]
[0, 3, 7, 4, 5, 6, 8, 9]
[0, 3, 6, 4, 5, 7, 8, 9]
[0, 3, 6, 4, 5, 7, 8, 9]
[0, 3, 6, 4, 5, 7, 8, 9]
[0, 3, 6, 4, 5, 7, 8, 9]
[0, 3, 6, 4, 5, 7, 8, 9]
[0, 3, 5, 4, 6, 7, 8, 9]
[0, 3, 5, 4, 6, 7, 8, 9]
[0, 3, 5, 4, 6, 7, 8, 9]
[0, 3, 4, 5, 6, 7, 8, 9]
[0, 3, 4, 5, 6, 7, 8, 9]
[0, 3, 4, 5, 6, 7, 8, 9]
[0, 3, 4, 5, 6, 7, 8, 9]

Further Reading