Heap Sort

Heap Sort


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) ...

Get Wicked Cool Ruby Scripts now with the O’Reilly learning platform.

O’Reilly members experience live online training, plus books, videos, and digital content from nearly 200 publishers.