Author(s)

Mahmoud Ragab¹, Beih El-Sayed El-Desouky², Nora Nader²

¹Department of Mathematies, Faculty of Science, Al Azhar University, Cairo, Egypt.
²Department of Mathematics, Faculty of Science, Mansoura University, Mansoura, Egypt.

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.

Randomized Quicksort, Convergence, Dual-Pivot Quicksort Process, Running Time Analysis

Ragab, M. , El-Desouky, B. and Nader, N. (2016) On the Convergence of the Dual-Pivot Quicksort Process. Open Journal of Modelling and Simulation, 4, 1-15. doi: 10.4236/ojmsi.2016.41001.