Research Repository

Dual Pivot Quicksort

Iliopoulos, V and Penman, DB (2012) 'Dual Pivot Quicksort.' Discrete Mathematics, Algorithms and Applications, 04 (03). creators - Penman=3ADavid_B=3A=3A. ISSN 1793-8309

[img]
Preview
Text
dual pivot Quicksort-postprint.pdf - Accepted Version

Download (112kB) | Preview

Abstract

In this paper, we analyze 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.

Item Type: Article
Uncontrolled Keywords: Quicksort; sorting algorithm
Subjects: Q Science > QA Mathematics
Divisions: Faculty of Science and Health > Mathematical Sciences, Department of
Depositing User: Jim Jamieson
Date Deposited: 10 Mar 2015 10:44
Last Modified: 17 Aug 2017 17:38
URI: http://repository.essex.ac.uk/id/eprint/13268

Actions (login required)

View Item View Item