Exploiting partial order with Quicksort
RG Dromey - Software: Practice and Experience, 1984 - Wiley Online Library
RG Dromey
Software: Practice and Experience, 1984•Wiley Online LibraryThe widely known Quicksort algorithm does not attempt to actively take advantage of partial
order in sorting data. A simple change can be made to the Quicksort strategy to give a
bestcase performance of n, for ordered data, with a smooth transition to O (n log n) for
random data. This algorithm (Transort) matches the performance of Sedgewick's claimed
best implementation of Quicksort for random data.
order in sorting data. A simple change can be made to the Quicksort strategy to give a
bestcase performance of n, for ordered data, with a smooth transition to O (n log n) for
random data. This algorithm (Transort) matches the performance of Sedgewick's claimed
best implementation of Quicksort for random data.
Abstract
The widely known Quicksort algorithm does not attempt to actively take advantage of partial order in sorting data. A simple change can be made to the Quicksort strategy to give a bestcase performance of n, for ordered data, with a smooth transition to O(n log n) for random data. This algorithm (Transort) matches the performance of Sedgewick's claimed best implementation of Quicksort for random data.
Wiley Online LibraryShowing the best result for this search. See all results