License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.AofA.2018.36
URN: urn:nbn:de:0030-drops-89295
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8929/
Go to the corresponding LIPIcs Volume Portal

Wild, Sebastian

Average Cost of QuickXsort with Pivot Sampling

pdf-format:
LIPIcs-AofA-2018-36.pdf (0.6 MB)

Abstract

QuickXsort is a strategy to combine Quicksort with another sorting method X so that the result has essentially the same comparison cost as X in isolation, but sorts in place even when X requires a linear-size buffer. We solve the recurrence for QuickXsort precisely up to the linear term including the optimization to choose pivots from a sample of k elements. This allows to immediately obtain overall average costs using only the average costs of sorting method X (as if run in isolation). We thereby extend and greatly simplify the analysis of QuickHeapsort and QuickMergesort with practically efficient pivot selection, and give the first tight upper bounds including the linear term for such methods.

BibTeX - Entry

@InProceedings{wild:LIPIcs:2018:8929,
  author =	{Sebastian Wild},
  title =	{{Average Cost of QuickXsort with Pivot Sampling}},
  booktitle =	{29th International Conference on Probabilistic,  Combinatorial and Asymptotic Methods for the Analysis of Algorithms  (AofA 2018)},
  pages =	{36:1--36:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-078-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{110},
  editor =	{James Allen Fill and Mark Daniel Ward},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/8929},
  URN =		{urn:nbn:de:0030-drops-89295},
  doi =		{10.4230/LIPIcs.AofA.2018.36},
  annote =	{Keywords: in-situ sorting, constant-factor optimal sorting, pivot sampling, QuickMergesort, QuickHeapsort, Quicksort recurrence, average-case analysis}
}

Keywords: in-situ sorting, constant-factor optimal sorting, pivot sampling, QuickMergesort, QuickHeapsort, Quicksort recurrence, average-case analysis
Collection: 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)
Issue Date: 2018
Date of publication: 18.06.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI