Implementing HEAPSORT with (n logn - 0.9n) and QUICKSORT with (n logn + 0.2n) comparisons
P. Edelkamp. Journal of Experimental Algorithmics (JEA), 7 (1,):
20(January 2002)
Abstract
With refinements to the WEAK-HEAPSORT algorithm we establish the general and practical relevant sequential sorting algorithm INDEX-WEAK-HEAPSORT with exactly n⌈log n⌉ - 2⌈log n⌉ + 1 ≤ n log n-0.9n comparisons and at most n log n + 0.1n 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-HEAPSORT and GREEDY-WEAK-HEAPSORT we discuss modifications for a smaller set of pending element transpositions.If extra space to create an index is not available, with QUICK-WEAK-HEAPSORT we propose an efficient QUICKSORT variant with n log n + 0.2n + o(n) comparisons on the average. Furthermore, we present data showing that WEAK-HEAPSORT, INDEX-WEAK-HEAPSORT and QUICK-WEAK-HEAPSORT compete with other performant QUICKSORT and HEAPSORT variants.
Description
Implementing HEAPSORT with (n logn - 0.9n) and QUICKSORT with (n logn + 0.2n) comparisons
%0 Journal Article
%1 stiegeler2002implementing
%A Edelkamp, Patrick Stiegeler Stefan
%C New York, NY, USA
%D 2002
%J Journal of Experimental Algorithmics (JEA)
%K 2013 heapsort quicksort seminar sorting
%N 1,
%P 20
%T Implementing HEAPSORT with (n logn - 0.9n) and QUICKSORT with (n logn + 0.2n) comparisons
%U http://portal.acm.org/citation.cfm?id=944618.944623&coll=Portal&dl=GUIDE&CFID=88775871&CFTOKEN=40392553
%V 7
%X With refinements to the WEAK-HEAPSORT algorithm we establish the general and practical relevant sequential sorting algorithm INDEX-WEAK-HEAPSORT with exactly n⌈log n⌉ - 2⌈log n⌉ + 1 ≤ n log n-0.9n comparisons and at most n log n + 0.1n 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-HEAPSORT and GREEDY-WEAK-HEAPSORT we discuss modifications for a smaller set of pending element transpositions.If extra space to create an index is not available, with QUICK-WEAK-HEAPSORT we propose an efficient QUICKSORT variant with n log n + 0.2n + o(n) comparisons on the average. Furthermore, we present data showing that WEAK-HEAPSORT, INDEX-WEAK-HEAPSORT and QUICK-WEAK-HEAPSORT compete with other performant QUICKSORT and HEAPSORT variants.
@article{stiegeler2002implementing,
abstract = {With refinements to the WEAK-HEAPSORT algorithm we establish the general and practical relevant sequential sorting algorithm INDEX-WEAK-HEAPSORT with exactly n⌈log n⌉ - 2⌈log n⌉ + 1 ≤ n log n-0.9n comparisons and at most n log n + 0.1n 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-HEAPSORT and GREEDY-WEAK-HEAPSORT we discuss modifications for a smaller set of pending element transpositions.If extra space to create an index is not available, with QUICK-WEAK-HEAPSORT we propose an efficient QUICKSORT variant with n log n + 0.2n + o(n) comparisons on the average. Furthermore, we present data showing that WEAK-HEAPSORT, INDEX-WEAK-HEAPSORT and QUICK-WEAK-HEAPSORT compete with other performant QUICKSORT and HEAPSORT variants. },
added-at = {2013-05-28T15:16:09.000+0200},
address = {New York, NY, USA},
author = {Edelkamp, Patrick Stiegeler Stefan},
biburl = {https://www.bibsonomy.org/bibtex/2c202d8ef86bd0bf6625d46261af6e5c0/jpba},
description = {Implementing HEAPSORT with (n logn - 0.9n) and QUICKSORT with (n logn + 0.2n) comparisons},
interhash = {ad3aca34be88883cdca44d3724e565bf},
intrahash = {c202d8ef86bd0bf6625d46261af6e5c0},
journal = {Journal of Experimental Algorithmics (JEA)},
key = {1084-6654},
keywords = {2013 heapsort quicksort seminar sorting},
month = {January},
number = {1,},
pages = 20,
timestamp = {2013-05-28T15:16:09.000+0200},
title = {Implementing HEAPSORT with (n logn - 0.9n) and QUICKSORT with (n logn + 0.2n) comparisons},
url = {http://portal.acm.org/citation.cfm?id=944618.944623&coll=Portal&dl=GUIDE&CFID=88775871&CFTOKEN=40392553},
volume = 7,
year = 2002
}