Instantly share code, notes, and snippets.

# wmwong/quicksort.rb Created Sep 30, 2013

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