Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
Sorting quickly
module QuickSort
def sort(array, options = {})
start_index = options[:start_index] || 0
end_index = options[:end_index] || array.length - 1
unless start_index >= end_index
# Randomly choose a pivot and swap with the end index.
pivot_index = rand(end_index - start_index + 1) + start_index
temp = array[end_index]
array[end_index] = array[pivot_index]
array[pivot_index] = temp
# Separate the array into elements less than or equal to the pivot, the pivot, and
# elements greater than the pivot.
# Note that this means the pivot will be in the correct place.
last_less_index = start_index - 1
(start_index...end_index).each do |i|
if array[i] <= array[end_index]
last_less_index += 1
temp = array[i]
array[i] = array[last_less_index]
array[last_less_index] = temp
end
end
last_less_index += 1
temp = array[end_index]
array[end_index] = array[last_less_index]
array[last_less_index] = temp
# Sort the elements less than or equal to the pivot.
sort(array, start_index: start_index, end_index: last_less_index - 1)
# Sort the elements greater than the pivot.
sort(array, start_index: last_less_index + 1, end_index: end_index)
end
end
end
require './quicksort'
require 'test/unit'
class QuickSortTest < Test::Unit::TestCase
include QuickSort
def test_sort
# Empty array.
array = []
sort(array)
assert(array.empty?)
# Single array.
array = [1]
sort(array)
assert_equal(1, array[0])
# Two elements.
array = [1, 2]
sort(array)
assert_equal(1, array[0])
assert_equal(2, array[1])
# Sorted array.
array = [1, 2, 3, 4, 5, 6]
sort(array)
assert_equal(1, array[0])
assert_equal(2, array[1])
assert_equal(3, array[2])
assert_equal(4, array[3])
assert_equal(5, array[4])
assert_equal(6, array[5])
# Reverse sorted array.
array = [6, 5, 4, 3, 2, 1]
sort(array)
assert_equal(1, array[0])
assert_equal(2, array[1])
assert_equal(3, array[2])
assert_equal(4, array[3])
assert_equal(5, array[4])
assert_equal(6, array[5])
# Arbitrary array.
array = [5, 2, 4, 1, 6, 3]
sort(array)
assert_equal(1, array[0])
assert_equal(2, array[1])
assert_equal(3, array[2])
assert_equal(4, array[3])
assert_equal(5, array[4])
assert_equal(6, array[5])
end
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment