Data Structures and Algorithms
|
Quick Sort - the last drop of performance
|
The recursive calls in quick sort are generally expensive on most
architectures - the overhead of any procedure call is
significant and reasonable improvements can be obtained with
equivalent
iterative algorithms.
Two things can be done to eke a little more performance out
of your processor when sorting:
-
Quick sort - in its usual recursive form -
has a reasonably high constant factor relative to a simpler
sort such as insertion sort.
Thus, when the partitions become small (n < ~10),
a switch to insertion sort for the small partition will
usually show a measurable speed-up.
(The point at which it becomes effective to switch to
the insertion sort is extremely sensitive to architectural
features and needs to be determined for any target
processor: although a value of ~10 is a reasonable
guess!)
-
Write the whole algorithm in an iterative form.
This is left for a tutorial exercise!
© John Morris, 1998