DUAL PIVOT QUICKSORT

DOI10.1142/S1793830912500413zbMATH Open1291.68158arXiv1503.08498MaRDI QIDQ3166751FDOQ3166751

Vasileios Iliopoulos, David B. Penman

Publication date: 15 October 2012

Published in: Discrete Mathematics, Algorithms and Applications (Search for Journal in Brave)

Abstract: In this paper, we analyse the dual pivot Quicksort, a variant of the standard Quicksort algorithm, in which two pivots are used for the partitioning of the array. We are solving recurrences of the expected number of key comparisons and exchanges performed by the algorithm, obtaining the exact and asymptotic total average values contributing to its time complexity. Further, we compute the average number of partitioning stages and the variance of the number of key comparisons. In terms of mean values, dual pivot Quicksort does not appear to be faster than ordinary algorithm.

Full work available at URL: https://arxiv.org/abs/1503.08498

zbMATH Keywords

Quicksortsorting algorithm

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Searching and sorting (68P10)

Cites Work

• Samplesort: A Sampling Approach to Minimal Storage Tree Sorting

Cited In (3)

• Using nonlinear difference equations to study Quicksort algorithms
• Optimal Partitioning for Dual Pivot Quicksort
• Title not available (Why is that?)

   Recommendations

• Optimal Partitioning for Dual-Pivot Quicksort 👍 👎
• Optimal Partitioning for Dual Pivot Quicksort 👍 👎
• Multi-Pivot Quicksort: Theory and Experiments 👍 👎
• Quicksort revisited 👍 👎
• Dual-Pivot Quicksort: Optimality, Analysis and Zeros of Associated Lattice Paths 👍 👎
• Average Case and Distributional Analysis of Dual-Pivot Quicksort 👍 👎
• Title not available (Why is that?) 👍 👎
• An Extended Note on the Comparison-optimal Dual-Pivot Quickselect 👍 👎
• External quicksort 👍 👎

This page was built for publication: DUAL PIVOT QUICKSORT

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3166751)