Quicksort in Ruby for dailykata.net

quicksort.rb

# This implementation works, but it does all comparisons twice
# and is not in-place, requiring extra memory and raising
# a stack overflow for large arrays.

def quicksort(array)
  return array if array.size <= 1
  pivot = array.pop
  less = array.select {|x| x <= pivot }
  greater = array.select {|x| x > pivot }
  quicksort(less) + [pivot] + quicksort(greater)
end

require "test/unit"

class TestQuickSort < Test::Unit::TestCase
 
  def test_simple
    assert_equal([1, 2, 3, 4, 5], quicksort([5, 3, 4, 1, 2]))
  end

  def test_random
    assert_equal([1..20], quicksort([1..20].shuffle))
  end
end