Analysis of Algorithms : An Active Learning Approach

82 SORTING ALGORITHMS

Using Equation 1.19, we get

Now, substituting lgN for d, we get

Now, we have to add together the construction and loop stages to get our final

result. This gives the equation

■ 3.5.2 Average-Case Analysis

To get the average-case analysis for heapsort, we will take a different approach.

Let’s consider the best case, where the values are initially in the array in the

reverse order. You should be able to see that this is automatically a correct heap.

This means that each call to FixHeap in the construction phase will do only

two comparisons to show the values are properly ordered. So, because Fix-

Heap is called for about one-half of the elements and each call does two com-

parisons, the construction stage does about N comparisons, which is the same

order as in the worst case.

Notice that no matter what order the elements are in at the start, after the

construction stage we always have a heap. So, in every case, the for loop will

have to execute the same number of times as in the worst case, because to get

the sorted values we have to take each element out of the heap and then fix the

heap. So, in the best case, heapsort does about N + N lg N comparisons. This

means that the best case is O(N lg N).

For heapsort, the best and worst cases are both O(N lg N). This can only

mean that the average case must also be O(N lg N).

Wloop()N = 2 []()d– 2 2 d++ 2 dN()– 2 d

Wloop()N =d 2 d+1– 2 d+2++ 42 dNd* – 2 d+1

Wloop()N = 2 dN* – 2 d+2+ 4

Wloop()N = 2lgNN– 2 lgN +^2 + 4

Wloop()N ==2lgNN–4lgN + 4 ON()lgN

WN()= Wconstruction()N +Wloop()N

WN()= 4 N–2lgN– 4 ++2lgNN–4lgN 4

WN()≈ 4 N+2lgNN()– 3

WN()= ON()lgN