%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>&#8968;log <i>n</i>&#8969; - 2^{&#8968;log <i>n</i>&#8969;} + 1 &#8804; <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>&#8968;log <i>n</i>&#8969; - 2^{&#8968;log <i>n</i>&#8969;} + 1 &#8804; <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 }