Access Restriction

Author Brodal, Gerth Stlting ♦ Fagerberg, Rolf ♦ Moruz, Gabriel
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2008
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Computer programming, programs & data
Subject Keyword Adaptive sorting ♦ Quicksort ♦ Branch mispredictions
Abstract Quicksort was first introduced in 1961 by Hoare. Many variants have been developed, the best of which are among the fastest generic-sorting algorithms available, as testified by the choice of Quicksort as the default sorting algorithm in most programming libraries. Some sorting algorithms are adaptive, i.e., they have a complexity analysis that is better for inputs, which are nearly sorted, according to some specified measure of presortedness. Quicksort is not among these, as it uses $Ω(\textit{n}$ log $\textit{n})$ comparisons even for sorted inputs. However, in this paper, we demonstrate empirically that the actual running time of Quicksort $\textit{is}$ adaptive with respect to the presortedness measure Inv. Differences close to a factor of two are observed between instances with low and high Inv value. We then show that for the randomized version of Quicksort, the number of element $\textit{swaps}$ performed is $\textit{provably}$ adaptive with respect to the measure Inv. More precisely, we prove that randomized Quicksort performs expected $\textit{O}(\textit{n}(1$ + log(1 + $Inv/\textit{n})))$ element swaps, where Inv denotes the number of inversions in the input sequence. This result provides a theoretical explanation for the observed behavior and gives new insights on the behavior of Quicksort. We also give some empirical results on the adaptive behavior of Heapsort and Mergesort.
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 2008-08-01
Publisher Place New York
e-ISSN 10846654
Journal Journal of Experimental Algorithmics (JEA)
Volume Number 12
Page Count 20
Starting Page 1
Ending Page 20

Open content in new tab

   Open content in new tab
Source: ACM Digital Library