Thumbnail
Access Restriction
Subscribed

Author Edelkamp, Stefan ♦ Stiegeler, Patrick
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2002
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Computer programming, programs & data
Abstract With refinements to the $\textit{WEAK-HEAPSORT}$ algorithm we establish the general and practical relevant sequential sorting algorithm $\textit{INDEX-WEAK-HEAPSORT}$ with exactly $\textit{n}⌈log$ $\textit{n}⌉$ - 2⌈log $\textit{n}⌉$ + 1 ≤ $\textit{n}$ log $\textit{n}-0.9\textit{n}$ comparisons and at most $\textit{n}$ log $\textit{n}$ + $0.1\textit{n}$ transpositions on any given input. It comprises an integer array of size $\textit{n}$ and is best used to generate an index for the data set. With $\textit{RELAXED-WEAK-HEAPSORT}$ and $\textit{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 $\textit{QUICK-WEAK-HEAPSORT}$ we propose an efficient $\textit{QUICKSORT}$ variant with $\textit{n}$ log $\textit{n}$ + $0.2\textit{n}$ + $\textit{o(n)}$ comparisons on the average. Furthermore, we present data showing that WEAK-HEAPSORT, INDEX-WEAK-HEAPSORT and $\textit{QUICK-WEAK-HEAPSORT}$ compete with other performant $\textit{QUICKSORT}$ and $\textit{HEAPSORT}$ variants.
ISSN 10846654
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2002-12-01
Publisher Place New York
e-ISSN 10846654
Journal Journal of Experimental Algorithmics (JEA)
Volume Number 7
Starting Page 5


Open content in new tab

   Open content in new tab
Source: ACM Digital Library