Created
August 4, 2016 02:54
-
-
Save ravelll/5c20744ff35c2ed9890ababd8f7c4a1a to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#!/usr/bin/env ruby | |
require 'benchmark' | |
class Array | |
def quick_sort | |
return self if self.length <= 1 | |
pivot = pop | |
left, right = partition { |e| e < pivot } | |
push pivot | |
left.quick_sort + [pivot] + right.quick_sort | |
end | |
def heap_sort! | |
build_heap | |
(size-1).downto(1) do |i| | |
self[0], self[i] = self[i], self[0] | |
heapify(0, i) | |
end | |
end | |
def build_heap | |
((size-1)/2).downto(0) do |i| | |
heapify(i) | |
end | |
end | |
def heapify(index, heap_size = size) | |
left = heap_left_child_index(index) | |
right = heap_right_child_index(index) | |
largest = index | |
largest = left if left < heap_size && self[left] > self[largest] | |
largest = right if right < heap_size && self[right] > self[largest] | |
if largest != index | |
self[largest], self[index] = self[index], self[largest] | |
heapify(largest, heap_size) | |
end | |
end | |
def heap_left_child_index(current_index) | |
current_index * 2 + 1 | |
end | |
def heap_right_child_index(current_index) | |
current_index * 2 + 2 | |
end | |
def merge_sort | |
tmp = self.dup | |
return tmp if tmp.length <= 1 | |
a, b = self.half.map { |e| e.merge_sort } | |
merge(a, b) | |
end | |
def half | |
mid = length/2 | |
return slice(0...mid), slice(mid..-1) | |
end | |
def merge(a, b) | |
res = [] | |
until a.empty? && b.empty? | |
res << | |
case | |
when a.empty? then b.shift | |
when b.empty? then a.shift | |
when a.first < b.first then a.shift | |
else b.shift | |
end | |
end | |
res | |
end | |
end | |
def nums | |
n = [] | |
1000000.times { n << rand(1000000000) } | |
n.uniq | |
end | |
n = nums | |
puts "Quick Sort: #{Benchmark.realtime { n.quick_sort } }" | |
puts "Merge Sort: #{Benchmark.realtime { n.merge_sort } }" | |
puts "Heap Sort: #{Benchmark.realtime { n.heap_sort! } }" |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment