按年被提到
20132013 · 1 次2026
算法与数据结构›经典算法与数据结构·arXiv:1303.5217 · cs.DS

Optimal Partitioning for Dual-Pivot Quicksort

Martin Aumüller, Martin Dietzfelbinger · 2013
开始阅读 ↗PDFalphaXiv 讨论
被提及 · 2 人首次 2013-03-25 · 最近 2017-10-11
2不同的人
2活跃月份
2讨论串
7被引(OpenAlex)
arXiv 摘要(候选层不写导读)

Dual-pivot quicksort refers to variants of classical quicksort where in the partitioning step two pivots are used to split the input into three segments. This can be done in different ways, giving rise to different algorithms. Recently, a dual-pivot algorithm proposed by Yaroslavskiy received much attention, because a variant of it replaced the well-engineered quicksort algorithm in Sun's Java 7 runtime library. Nebel and Wild (ESA 2012) analyzed this algorithm and showed that on average it uses 1.9n ln n + O(n) comparisons to sort an input of size n, beating standard quicksort, which uses 2n ln n + O(n) comparisons. We introduce a model that captures all dual-pivot algorithms, give a unified analysis, and identify new dual-pivot algorithms that minimize the average number of key comparisons among all possible algorithms up to a linear term. This minimum is 1.8n ln n + O(n). For the case that the pivots are chosen from a small sample, we include a comparison of dual-pivot quicksort and classical quicksort. Specifically, we show that dual-pivot quicksort benefits from a skewed choice of pivots. We experimentally evaluate our algorithms and compare them to Yaroslavskiy's algorithm and the recently described three-pivot quicksort algorithm of Kushagra et al. (ALENEX 2014).

候选层:至少 2 个不同的人、在 2 个不同月份提到过,还没到主书架的 3 人 3 个月。没有做立场标注,所以只写“被提及”。

HN 书评

推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及
评论thomasahle · 2017-10

“Your article [1] isn't a real published article, and it doesn't have a proper analysis. For somebody who has actually done the work, and gotten it published, see https://arxiv.org/pdf/1303.5217.pdf”

Quicksort (1961) [pdf]原评论 ↗
被提交为 story · 1 次