November 2008
Intermediate to advanced
208 pages
4h 32m
English
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.
require 'benchmark'
def heap_sort(a)
size = a.length
temp = 0
i = (size/2)-1
while i >= 0 sift_down(a,i,size) ...Read now
Unlock full access