 | The ACM Journal of Experimental Algorithmics |
Volume 7, Article 5, 2002
Implementing HEAPSORT with (n logn - 0.9n) and QUICKSORT
with (n logn + 0.2n) Comparisons
by
and
http://www.jea.acm.org/2002/EdelkampHeapsort/
Abstract:
With refinements to the weak-heap-sort algorithm we establish
the general and practically relevant sequential sorting
algorithm index-weak-heap-sort with exactly
n ceiling(log n) - 2ceiling(log n) +1 <= n log n
- 0.9 n comparisons and at most n log n + 0.1 n transpositions
on any given input. It comprises an integer array of size
n and is best used to generate an index for the data set.
With relaxed-weak-heap-sort and greedy-weak-heap-sort
we discuss modifications for a smaller set of
pending element transpositions.
If extra space to create an index is not available,
with quick-weak-heap-sort we propose an efficient quicksort variant
with n log n + 0.2 n + o(n) comparisons on the average.
Furthermore, we present data showing that
weak-heap-sort, index-weak-heap-sort, and quick-weak-heap-sort compete
with other performant quicksort and heapsort variants.
- Sources:
- The LaTeX version of the article;
this is a Unix file that contains the LaTeX source;
note that you must be a subscriber (institutional or individual) to access this file.
- The Postscript
version or PDF
version of the article;
note that you must be a subscriber (institutional or individual) to access
these files.
- The HTML version of the article;
note that you must be a subscriber (institutional or individual) to access
this file.
- The software suite accompanying the
article; this is a small Unix tar file, which includes the source code,
a Makefile, and the test files used in the article.
- The bibliography given in the article.
Received
|
Accepted
|
Final Revision
|
Published
|
|
|
|
|
Last updated and validated May 11, 2002, by editor@jea.acm.org