#gunmacs QuickSort

gistfile1.rb

require 'pry'
require 'test/unit'

class Array
  def quick_sort
    ary = self.dup
    return ary if size <= 1

    left, right = ary.partition_by_pivot_index(ary.pivot_index)
    left.quick_sort + right.quick_sort
  end

  def pivot_index
    n = self.first
    self.each_with_index do |value, index|
      return index if n < value
    end

    0
  end

  def partition_by_pivot_index(pivot_index)
    p = self[pivot_index]
    left = []
    right = []

    if self.same_values?
      return [self[0, (size / 2)], self[(size / 2), size]]
    end

    self.each do |n|
      if n < p
        left << n
      else
        right << n
      end
    end

    [left, right]
  end

  def same_values?
    n = self.first
    self.each {|v| return false if n != v}
    true
  end
end

class ArrayTest < Test::Unit::TestCase
  def test_quick_sort
    assert_equal([], [].quick_sort)
    assert_equal([1], [1].quick_sort)
    assert_equal([1, 2], [2, 1].quick_sort)
    assert_equal([1, 2, 3, 4], [2, 4, 3, 1].quick_sort)
    assert_equal([1, 2, 3, 4, 5], [5, 2, 4, 3, 1].quick_sort)
    assert_equal([1, 2, 3, 3, 4, 5], [5, 2, 3, 4, 3, 1].quick_sort)
  end

  def test_pivot_index
    assert_equal(1, [1, 2].pivot_index)
    assert_equal(0, [4, 2, 3].pivot_index)
    assert_equal(2, [3, 2, 5, 4].pivot_index)
  end

  def test_partition_by_pivot
    assert_equal([[1], [2]], [1, 2].partition_by_pivot_index(1))
    assert_equal([[3], [3]], [3, 3].partition_by_pivot_index(0))
    assert_equal([[1, 2], [4, 3]], [4, 1, 3, 2].partition_by_pivot_index(2))
  end

  def test_same_values?
    assert_equal(true, [3, 3].same_values?)
    assert_equal(false, [3, 2].same_values?)
  end
end