publication . Part of book or chapter of book . Conference object . Preprint . 2013

Average case analysis of java 7's dual pivot quicksort

Wild, Sebastian; Nebel, Markus E.;
Open Access
  • Published: 28 Oct 2013
  • Publisher: Springer Berlin Heidelberg
  • Country: United Kingdom
Abstract
Comment: Best paper award at ESA 2012, recorded talk: http://www.slideshare.net/sebawild/average-case-analysis-of-java-7s-dual-pivot-quicksort
Subjects
free text keywords: Oracle, Mathematics, Quicksort, Java, computer.programming_language, computer, Expected value, Combinatorics, Sorting, Random permutation, Pivot element, Discrete mathematics, Introsort, Computer Science - Data Structures and Algorithms, Mathematics - Probability
Related Organizations

[1] Jon L. Bentley and M. Douglas McIlroy. Engineering a sort function. Software: Practice and Experience, 23(11):1249-1265, 1993.

[2] Guy E. Blelloch, Charles E. Leiserson, Bruce M. Maggs, C. Greg Plaxton, Stephen J. Smith, and Marco Zagha. A comparison of sorting algorithms for the connection machine CM-2. In Annual ACM symposium on Parallel algorithms and architectures, pages 3-16, New York, USA, June 1991. ACM Press.

[3] W. D. Frazer and A. C. McKellar. Samplesort: A Sampling Approach to Minimal Storage Tree Sorting. Journal of the ACM, 17(3):496-507, July 1970.

[4] Pascal Hennequin. Combinatorial analysis of Quicksort algorithm. Informatique théorique et applications, 23(3):317-333, 1989.

[5] Pascal Hennequin. Analyse en moyenne d'algorithmes : tri rapide et arbres de recherche. PhD Thesis, Ecole Politechnique, Palaiseau, 1991.

[6] C. A. R. Hoare. Algorithm 63: Partition. Communications of the ACM, 4(7):321, July 1961.

[7] C. A. R. Hoare. Quicksort. The Computer Journal, 5(1):10-16, January 1962.

[8] Ulrich Laube and Markus E. Nebel. Maximum likelihood analysis of algorithms and data structures. Theoretical Computer Science, 411(1):188-212, January 2010.

[9] Nikolaj Leischner, Vitaly Osipov, and Peter Sanders. GPU sample sort. In 2010 IEEE International Symposium on Parallel Distributed Processing IPDPS, pages 1-10. IEEE, 2009. [OpenAIRE]

[10] Peter Sanders and Sebastian Winkel. Super Scalar Sample Sort. In Susanne Albers and Tomasz Radzik, editors, ESA 2004. LNCS, vol. 3221, pages 784-796. Springer Berlin/Heidelberg, 2004.

[11] Robert Sedgewick. Quicksort. PhD Thesis, Stanford University, 1975.

[12] Robert Sedgewick. Quicksort with Equal Keys. SIAM Journal on Computing, 6(2):240-267, 1977.

[13] Robert Sedgewick. The analysis of Quicksort programs. Acta Inf., 7(4):327-355, 1977.

[14] Robert Sedgewick. Implementing Quicksort programs. Communications of the ACM, 21(10):847-857, October 1978.

Case 2, as G is the same in Case 1 and 2. In summary, we find an additional contribution of nn−−2q to spn,q.

Powered by OpenAIRE Research Graph
Any information missing or wrong?Report an Issue