Bogosort in Ruby

Overview

Bogosort ("Bogus" + "sort") is an intentionally inefficient algorithm for sorting which randomly shuffles the list until it is correctly sorted. It is not seriously used for any purpose but rather is interesting only in comparison to more efficient algorithms.

Concise

def bogosort(a)
  until sorted?(a)
    p a
    a = a.shuffle
  end

  a
end

def sorted?(a)
  s = true

  (a.length-1).times do |i|
    if a[i] > a[i+1]
      s = false
    end
  end

  s
end

u = (1..5).to_a.sort{ rand() - 0.5 }[0..9]
puts u.inspect

s = bogosort(u)
puts s.inspect
bogosort.rb

Verbose

# Bogosort in Ruby
#
# Input: A sequence of numbers in any order.
# Output: An ordered sequence from smallest number to largest.
#
def bogosort(numbers)

  # Keep shuffling the array until it is sorted.
  until sorted?(numbers)
    p numbers
    numbers = numbers.shuffle
  end

  numbers
end

# Checks to see whether array is sorted.
def sorted?(array)
  sorted = true

  # Iterates through the array and invalidates that the array is sorted
  # if it finds an instance where elements are out of order.
  (array.length-1).times do |i|
    if array[i] > array[i+1]
      sorted = false
    end
  end

  sorted
end

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

# Sort.
sorted = bogosort(unsorted)
puts sorted.inspect
bogosort_verbose.rb

Sample Input and Output

$ ruby bogosort.rb
[5, 2, 4, 3, 1]
[5, 2, 4, 3, 1]
[1, 4, 2, 3, 5]
[1, 3, 2, 4, 5]
[2, 5, 4, 3, 1]
[4, 2, 1, 5, 3]
[3, 1, 2, 5, 4]
[3, 4, 1, 2, 5]
[2, 5, 3, 4, 1]
[4, 2, 1, 3, 5]
[1, 4, 5, 2, 3]
[2, 5, 4, 3, 1]
[5, 4, 1, 3, 2]
[3, 2, 1, 4, 5]
[1, 2, 3, 5, 4]
[2, 3, 1, 4, 5]
[1, 3, 2, 4, 5]
[4, 1, 3, 5, 2]
[5, 1, 3, 4, 2]
[1, 4, 2, 3, 5]
[2, 5, 4, 1, 3]
[3, 5, 4, 1, 2]
[3, 4, 2, 1, 5]
[1, 4, 2, 5, 3]
[2, 5, 3, 1, 4]
[5, 4, 3, 2, 1]
[3, 2, 1, 5, 4]
[5, 3, 2, 4, 1]
[1, 5, 4, 3, 2]
[4, 3, 1, 5, 2]
[2, 1, 3, 5, 4]
[4, 1, 5, 2, 3]
[1, 5, 3, 4, 2]
[5, 3, 2, 4, 1]
[1, 2, 4, 5, 3]
[2, 4, 1, 3, 5]
[2, 1, 4, 5, 3]
[5, 1, 2, 4, 3]
[4, 2, 1, 3, 5]
[4, 3, 5, 1, 2]
[5, 4, 2, 1, 3]
[1, 5, 3, 2, 4]
[2, 1, 3, 5, 4]
[1, 3, 5, 2, 4]
[2, 3, 5, 1, 4]
[4, 3, 5, 2, 1]
[5, 2, 3, 1, 4]
[4, 2, 3, 5, 1]
[1, 2, 3, 5, 4]
[3, 1, 5, 2, 4]
[2, 3, 4, 1, 5]
[1, 3, 4, 5, 2]
[2, 3, 5, 1, 4]
[4, 2, 5, 3, 1]
[5, 1, 2, 4, 3]
[4, 2, 5, 1, 3]
[3, 1, 5, 2, 4]
[4, 1, 3, 5, 2]
[5, 1, 3, 2, 4]
[5, 4, 2, 3, 1]
[3, 5, 4, 2, 1]
[4, 2, 5, 3, 1]
[5, 2, 3, 4, 1]
[5, 3, 4, 2, 1]
[1, 4, 2, 5, 3]
[1, 4, 3, 2, 5]
[2, 4, 5, 3, 1]
[4, 1, 3, 5, 2]
[4, 1, 2, 3, 5]
[2, 1, 4, 3, 5]
[3, 1, 4, 5, 2]
[2, 3, 1, 4, 5]
[5, 2, 4, 1, 3]
[2, 4, 5, 1, 3]
[4, 3, 5, 1, 2]
[1, 2, 3, 4, 5]

Further Reading

Wikipedia - Bogosort