|
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.
| 
Search