With refinements to the <i>WEAK-HEAPSORT</i> algorithm we establish the general and practical relevant sequential sorting algorithm <i>INDEX-WEAK-HEAPSORT</i> with exactly <i>n</i>⌈log <i>n</i>⌉ - 2<sup>⌈log <i>n</i>⌉</sup> + 1 ≤ <i>n</i> log <i>n</i>-0.9<i>n</i> comparisons and at most <i>n</i> log <i>n</i> + 0.1<i>n</i> transpositions on any given input. It comprises an integer array of size <i>n</i> and is best used to generate an index for the data set. With <i>RELAXED-WEAK-HEAPSORT</i> and <i>GREEDY-WEAK-HEAPSORT</i> we discuss modifications for a smaller set of pending element transpositions.If extra space to create an index is not available, with <i>QUICK-WEAK-HEAPSORT</i> we propose an efficient <i>QUICKSORT</i> variant with <i>n</i> log <i>n</i> + 0.2<i>n</i> + <i>o(n)</i> comparisons on the average. Furthermore, we present data showing that <i>WEAK-HEAPSORT, INDEX-WEAK-HEAPSORT</i> and <i>QUICK-WEAK-HEAPSORT</i> compete with other performant <i>QUICKSORT</i> and <i>HEAPSORT</i> variants.
%0 Journal Article
%1 Edelkamp:2002:IHN:944618.944623
%A Edelkamp, Stefan
%A Stiegeler, Patrick
%C New York, NY, USA
%D 2002
%I ACM
%J J. Exp. Algorithmics
%K heapsort logn quicksort
%P 5--
%R 10.1145/944618.944623
%T Implementing HEAPSORT with (n logn - 0.9n) and QUICKSORT with (n logn + 0.2n) comparisons
%U http://doi.acm.org/10.1145/944618.944623
%V 7
%X With refinements to the <i>WEAK-HEAPSORT</i> algorithm we establish the general and practical relevant sequential sorting algorithm <i>INDEX-WEAK-HEAPSORT</i> with exactly <i>n</i>⌈log <i>n</i>⌉ - 2<sup>⌈log <i>n</i>⌉</sup> + 1 ≤ <i>n</i> log <i>n</i>-0.9<i>n</i> comparisons and at most <i>n</i> log <i>n</i> + 0.1<i>n</i> transpositions on any given input. It comprises an integer array of size <i>n</i> and is best used to generate an index for the data set. With <i>RELAXED-WEAK-HEAPSORT</i> and <i>GREEDY-WEAK-HEAPSORT</i> we discuss modifications for a smaller set of pending element transpositions.If extra space to create an index is not available, with <i>QUICK-WEAK-HEAPSORT</i> we propose an efficient <i>QUICKSORT</i> variant with <i>n</i> log <i>n</i> + 0.2<i>n</i> + <i>o(n)</i> comparisons on the average. Furthermore, we present data showing that <i>WEAK-HEAPSORT, INDEX-WEAK-HEAPSORT</i> and <i>QUICK-WEAK-HEAPSORT</i> compete with other performant <i>QUICKSORT</i> and <i>HEAPSORT</i> variants.
@article{Edelkamp:2002:IHN:944618.944623,
abstract = {With refinements to the <i>WEAK-HEAPSORT</i> algorithm we establish the general and practical relevant sequential sorting algorithm <i>INDEX-WEAK-HEAPSORT</i> with exactly <i>n</i>⌈log <i>n</i>⌉ - 2<sup>⌈log <i>n</i>⌉</sup> + 1 ≤ <i>n</i> log <i>n</i>-0.9<i>n</i> comparisons and at most <i>n</i> log <i>n</i> + 0.1<i>n</i> transpositions on any given input. It comprises an integer array of size <i>n</i> and is best used to generate an index for the data set. With <i>RELAXED-WEAK-HEAPSORT</i> and <i>GREEDY-WEAK-HEAPSORT</i> we discuss modifications for a smaller set of pending element transpositions.If extra space to create an index is not available, with <i>QUICK-WEAK-HEAPSORT</i> we propose an efficient <i>QUICKSORT</i> variant with <i>n</i> log <i>n</i> + 0.2<i>n</i> + <i>o(n)</i> comparisons on the average. Furthermore, we present data showing that <i>WEAK-HEAPSORT, INDEX-WEAK-HEAPSORT</i> and <i>QUICK-WEAK-HEAPSORT</i> compete with other performant <i>QUICKSORT</i> and <i>HEAPSORT</i> variants.},
acmid = {944623},
added-at = {2012-05-03T17:57:01.000+0200},
address = {New York, NY, USA},
author = {Edelkamp, Stefan and Stiegeler, Patrick},
biburl = {https://www.bibsonomy.org/bibtex/23078f08f68c788cab93cb2f93a239296/bjoern},
doi = {10.1145/944618.944623},
interhash = {2fc93164f967489ad02e5c2820408790},
intrahash = {3078f08f68c788cab93cb2f93a239296},
issn = {1084-6654},
issue_date = {2002},
journal = {J. Exp. Algorithmics},
keywords = {heapsort logn quicksort},
month = dec,
pages = {5--},
publisher = {ACM},
timestamp = {2012-05-03T17:58:29.000+0200},
title = {Implementing HEAPSORT with (n logn - 0.9n) and QUICKSORT with (n logn + 0.2n) comparisons},
url = {http://doi.acm.org/10.1145/944618.944623},
volume = 7,
year = 2002
}