On the adaptiveness of Quicksort
Autor: | Gabriel Moruz, Gerth Stølting Brodal, Rolf Fagerberg |
---|---|
Přispěvatelé: | Demetrescu, I.C., Tamassia, R. |
Rok vydání: | 2008 |
Předmět: | |
Zdroj: | Aarhus University Brodal, G S, Fagerberg, R & Moruz, G 2005, On the Adaptiveness of Quicksort . in I C Demetrescu & R Tamassia (eds), Proceeding of the 7 th Workshop on Algorithm Engineering and Experiments . Society for Industrial and Applied Mathematics, pp. 130-140, The 7 th Workshop on Algorithm Engineering and Experiments, 24/08/2010 . Brodal, G S, Fagerberg, R & Moruz, G 2008, ' On the adaptiveness of Quicksort ', ACM Journal of Experimental Algorithmics, vol. 12 . https://doi.org/10.1145/1227161.1402294 Scopus-Elsevier Brodal, G S, Fagerberg, R & Moruz, G 2005, On the Adaptiveness of Quicksort . in ALENEX05 . Society for Industrial and Applied Mathematics, pp. 130-140, Workshop on Algorithm Engineering and Experiments, Vancouver, B.C., Canada, 22/01/2005 . Brodal, G S, Fagerberg, R & Moruz, G 2008, ' On the Adaptiveness of Quicksort ', Journal of Experimental Algorithmics, vol. 12 . https://doi.org/10.1145/1227161.1402294 BRICS Report Series; No 27 (2004): RS-27 On the Adaptiveness of Quicksort BRICS Report Series; Nr. 27 (2004): RS-27 On the Adaptiveness of Quicksort Brodal, G S, Fagerberg, R & Moruz, G 2004, ' On the Adaptiveness of Quicksort ', B R I C S Report Series, no. RS-04-27 . |
ISSN: | 1084-6654 1601-5355 0909-0878 |
DOI: | 10.1145/1227161.1402294 |
Popis: | 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 Ω( n log n ) comparisons even for sorted inputs. However, in this paper, we demonstrate empirically that the actual running time of Quicksort 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 swaps performed is provably adaptive with respect to the measure Inv. More precisely, we prove that randomized Quicksort performs expected O ( n (1 + log(1 + Inv/ 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. |
Databáze: | OpenAIRE |
Externí odkaz: |