Wicked Cool Ruby Scripts

Heap Sort

Heap Sort

heapSort.rb

Building on the selection sort, heap sort uses the selections much more efficiently, as can be seen in a comparison of the two execution times. Heap sort is comparable to the quick sort algorithm shown in the next section, but typically, quick sort will have a faster execution time. The difference in the two sorting routines is in the worst-case Big O scenario, where heap sort edges out quick sort. In most implementations, the worst case is not the normal case, so it is up to you to consider the consequences.

The Code

 require 'benchmark'

 def heap_sort(a)
     size = a.length
     temp = 0
     i = (size/2)-1

 while i >= 0 sift_down(a,i,size) ...