TITLE:
On the Convergence of the Dual-Pivot Quicksort Process
AUTHORS:
Mahmoud Ragab, Beih El-Sayed El-Desouky, Nora Nader
KEYWORDS:
Randomized Quicksort, Convergence, Dual-Pivot Quicksort Process, Running Time Analysis
JOURNAL NAME:
Open Journal of Modelling and Simulation,
Vol.4 No.1,
January
29,
2016
ABSTRACT: Sorting an array of objects such as integers, bytes, floats, etc is considered as one of the most important problems in Computer Science. Quicksort is an effective and wide studied sorting algorithm to sort an array of n distinct elements using a single pivot. Recently, a modified version of the classical Quicksort was chosen as standard sorting algorithm for Oracles Java 7 routine library due to Vladimir Yaroslavskiy. The purpose of this paper is to present the different behavior of the classical Quicksort and the Dual-pivot Quicksort in complexity. In Particular, we discuss the convergence of the Dual-pivot Quicksort process by using the contraction method. Moreover we show the distribution of the number of comparison done by the duality process converges to a unique fixed point.