UP ONE LEVEL:
ENEL 315 Home Page
Efficiency of Quicksort
ENEL 315 Class Handout, Winter 1996
Author:
Steve Norman
Date of first publication: 20 March 1996
Last modified: Wed Mar 20 11:35:00 MST 1996
Contents
Revision History
[back to top of document]
Introduction and Warning
This handout
is a supplement to the lecture of Wednesday, March 20.
See your lecture notes for additional remarks about this handout.
This handout is NOT a rigorous analysis of quicksort.
It doesn't really give proofs of results - it just
gives sketches of proofs.
[back to top of document]
The only significant cost is partitioning
For large arrays, it's a fact that almost all of the time
spent by quicksort is spent partitioning sub-arrays.
For a sub-array of length n,
the partitioning time is somewhere between
a n + c
and b n + c,
where a, b and c are
positive constants,
and a < b.
The constant c reflects the fact that a certain
amount of work has to be done regardless of the
array length.
This includes function call and return overhead and
initialization of local variables, and so on.
The shortest possible time is taken when no
elements have to be swapped.
Even in this case, there is work to do, because
the pivot value has to be compared to all the
other elements, and each comparison takes a certain amount of time.
So the lower bound on
partitioning time is of the form a n + c.
The longest possible time is taken when there are a lot
of swaps.
The largest number of swaps possible is about n/2,
which says that the upper bound on
partitioning time is of the form b n + c.
[back to top of document]
Best-case running time
This section gives an example of near-optimal performance
of quicksort.
(One could cook up an array which required less
swapping during partitioning of sub-arrays.)
In this case, we naively choose the first element of
the sub-array to be the pivot, and it works out perfectly.
Each partitioning cuts a sub-array in half.
The number n can be cut in half about
log n times before a value of about 1 is reached.
(Remember, base 2 is used for logarithms in computer science.)
This leads to the picture below.
The diagram below is not the same as the one that appears
in the paper version of this handout.
The diagram below shows the sub-arrays as they would evolve
using the partition algorithm given in the lecture
on Monday, March 18.
Adding up all the partitioning time gives an upper bound of
b n log n + c n / 2
on the total running time.
[back to top of document]
Worst-case running time
This section shows why naively choosing the
first element as the pivot leads to disastrously slow performance
on arrays that are already ordered.
Consider this picture:
As noted earlier, partitioning takes significant time even
when no array elements are moved.
Adding up all the partitioning time and throwing away
some insignificant terms gives a lower bound of
a n n / 2 + c n
on the total running time.
That's not really a problem for an array of 15 elements,
but's a very big problem for an array of 10,000 elements.
[back to top of document]