Quicksort in Ruby using TDD

quicksort_test.rb

require 'test/unit'

def sort(list)
  return [] if list.size == 0
  return list if list.size == 1

  pivot     = list[0]
  remaining = list[1..-1]

  smaller, larger = partition(pivot, remaining)

  sort(smaller) + [pivot] + sort(larger)
end

def partition(pivot, list, smaller = [], larger = [])
  return [smaller, larger] if list.size == 0

  tail, next_smaller, next_larger = next_partition(pivot, list, smaller, larger)

  partition(pivot, tail, next_smaller, next_larger)
end

def next_partition(pivot, list, smaller, larger)
  head = list[0]
  tail = list[1..-1]

  if head <= pivot
    [tail, [head] + smaller, larger]
  else
    [tail, smaller, [head] + larger]
  end
end

class QuicksortTest < Test::Unit::TestCase
  def test_sorting_one_number_only
    assert_equal [8], sort([8])
  end

  def test_sorting_two_numbers
    assert_equal [1, 5], sort([5, 1])
  end

  def test_sorting_multiple_numbers
    assert_equal [1, 2, 3, 4, 5], sort([5, 3, 1, 2, 4])
    assert_equal [1, 2, 3, 4, 5], sort([3, 5, 1, 4, 2])
    assert_equal [1, 1, 3, 5, 8], sort([3, 1, 8, 1, 5])
  end

  def test_partition_no_remaining
    assert_equal [[3, 1], [8, 6, 7]], partition(5, [], [3, 1], [8, 6, 7])
  end

  def test_partition_two_numbers
    assert_equal [[], [5]], partition(1, [5])
  end

  def test_partition_three_numbers
    assert_equal [[], [6, 8]], partition(3, [8, 6])
  end

  def test_partition_multiple_numbers_using_different_pivots
    assert_equal [[3, 1, 2], [7, 5, 6]], partition(4, [2, 1, 6, 3, 5, 7])
    assert_equal [[5, 6, 3, 2, 1, 4], []], partition(7, [4, 1, 2, 3, 6, 5])
    assert_equal [[2, 1], [7, 5, 6, 4]], partition(3, [4, 1, 2, 6, 5, 7])
  end

  def test_partitions_in_details
    # list: [3, 5, 1, 4, 2]
    # pivot: 2

    assert_equal [[5, 1, 4], [], [3]], next_partition(2, [3, 5, 1, 4], [], [])
    assert_equal [[1, 4], [], [5, 3]], next_partition(2, [5, 1, 4], [], [3])
    assert_equal [[4], [1], [5, 3]], next_partition(2, [1, 4], [], [5, 3])
    assert_equal [[], [1], [4, 5, 3]], next_partition(2, [4], [1], [5, 3])

    # list: [4, 5, 3]
    # pivot: 5

    assert_equal [[3], [4], []], next_partition(5, [4, 3], [], [])
    assert_equal [[], [3, 4], []], next_partition(5, [3], [4], [])
  end
end