Algorithms

quick_sort.rb

require "test/unit/assertions"
include Test::Unit::Assertions

def quick_sort(array)
  return array if array.size == 0 || array.size == 1

  left_pointer = 0

  pivot = array.last
  pivot_index = array.size - 1

  for right_pointer in 0...(array.size - 1) do
    if array[right_pointer] <= pivot
      array = swap(array, left_pointer, right_pointer)
      left_pointer += 1
    end
  end

  array = swap(array, left_pointer, pivot_index)
  left = left_pointer == 0 ? [] : quick_sort(array[0..left_pointer - 1])
  right = quick_sort(array[left_pointer + 1..pivot_index])

  return left
    .concat([pivot])
    .concat(right)
end

def swap(array, a, b)
  temp = array[a]
  array[a] = array[b]
  array[b] = temp
  array
end

assert_equal quick_sort([3, 7, 8, 2, 1]), [1, 2, 3, 7, 8]
assert_equal quick_sort([3, 4, 5, 8, 9, 7]), [3, 4, 5, 7, 8, 9]
assert_equal quick_sort([3, 1, 3, 8, 9, 7]), [1, 3, 3, 7, 8, 9]
assert_equal quick_sort([2, 1]), [1, 2]