92 SORTING ALGORITHMS
So, how does quicksort do in removing inversions? Consider a list of N ele-
ments that the PivotList algorithm is working on. Let’s say that the Pivot-
Value is greater than all of the values in the list. This means that at the end of
the routine PivotPoint will be N, and so the PivotValue will be switched
from the first location to the last location. It is also possible that the element in
the last location is the smallest value in the list. So swapping these two values
will move the largest element from the first location to the last and will move
the smallest element from the last location to the first. If the largest element is
first, there are N 1 inversions of it with the rest of the elements in the list,
and if the smallest element is last, there are N 1 inversions of it with the rest
of the elements in the list. This one swap can remove 2N 2 inversions from
the list. It is because of this possibility that quicksort has an average case that is
significantly different from its worst case.
Notice that PivotList is doing all of the work, and so we first look at this
algorithm to see what it does in the average case. We first notice that it is possi-
ble for each of the N locations in the list to be the location of the Pivot-
Value when PivotList is done. To get the average case, we have to look at
what happens for each of these possibilities and average the results. When look-
ing at the worst case, we noticed that for a list of N elements there are N 1
comparisons done by PivotList in dividing the list. There is no work done
to put the lists back together. Lastly, notice that when PivotList returns a
value of P, we call Quicksort recursively with lists of P 1 and NP ele-
ments. Our average case analysis needs to look at all N possible values for P.
Putting this together gives the recurrence relationIf you look closely at the summation, you will notice that the first term is
used with values from 0 through N 1, and the second term is used with val-
ues from N 1 down to 0. This means that the summation adds up every
value of A from 0 to N 1 twice. This gives us the following simplification:AN() ()N– (^1) N----^1 []Ai()– 1 +AN i()–
i=1
N
∑
= + forN≥ 2
A() 1 ==A() 0 0
AN() ()N– (^1) N----^12 Ai()
i=0
N–1
∑
= + forN≥ 2
A() 1 ==A() 0 0