next up previous contents index Search
Next: Source Code Up: 0.3.1 The Quicksort Previous: Analysis Improvement Strategies

Some improvements can be made to the Quicksort by bolstering its weaknesses. The Quicksort does not perform well for small data sets. While your first instinct may be to ignore this limitation because you are ``always going to be sorting large arrays'' you should be remember that, as the algorithm divides your large array into smaller partitions, eventually it will reach a point that is is sorting a small array. The performance of the Quicksort can be enhanced if, for small partitions, it does not call itself recursively. Rather, calling another sort algorithm to handle the small data set can substantially decrease running time.    

Another way to accomplish this same optimization is to just stop sorting when your partitions reach a certain (small) size. Your final product will be a data set that is in ``almost'' sorted order. A few data items will be out of place here and there but never by much. Such an ``almost sorted'' array can then be fed through an Insertion Sort and put into final order. Because the Insertion Sort runs in near linear time for ``almost sorted'' data, this last step will normally prove to be much faster than continuing to sort every little partition recursively with a Quicksort.  

Yet another Quicksort improvement strategy which pertains especially to recursive implementations of the algorithm is to always process the smallest partition first. This results in more efficient use of the call stack and overall faster execution.

Scott Gasch