Skip to content

Instantly share code, notes, and snippets.

@adamjgrant
Last active November 4, 2016 01:17
Show Gist options
  • Save adamjgrant/b0af5f9b938b3ac8f6b56e424ff8b978 to your computer and use it in GitHub Desktop.
Save adamjgrant/b0af5f9b938b3ac8f6b56e424ff8b978 to your computer and use it in GitHub Desktop.
Quicksort, mergesort, etc.
require 'benchmark'
def quick_sort(array)
return array if array.size <= 1
pivot ||= array.shift
left = array.select { |n| n < pivot }
right = array.select { |n| n >= pivot }
return [*quick_sort(left), pivot, *quick_sort(right)]
end
def merge_sort(array)
return array if array.size <= 1
left, right = array.each_slice((array.size/2.0).round).to_a
merge = -> (left, right) {
array = []
while left.size > 0 && right.size > 0
array << (left[0] < right[0] ? left.shift : right.shift)
end
return array + left + right
}
return merge.call merge_sort(left), merge_sort(right)
end
array = (1..100).to_a.shuffle
sorted_array = array.sort
merge_sorted_array = merge_sort(array)
quick_sorted_array = quick_sort(array)
puts (sorted_array == quick_sorted_array ? "QS: Pass": "QS: Fail")
puts (sorted_array == merge_sorted_array ? "MS: Pass": "MS: Fail ")
puts "Quick sort : #{quick_sort(array) * ", "}"
puts "Default sort: #{array.sort * ", "}"
puts "Merge sort : #{merge_sort(array) * ", "}"
puts "Quick sort : #{puts Benchmark.measure { quick_sort(array) } }"
puts "Default sort: #{puts Benchmark.measure { array.sort } }"
puts "Merge sort: #{puts Benchmark.measure { merge_sort(array) } }"
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment