On the Convergence of the Dual-Pivot Quicksort Process
On the Convergence of the Dual-Pivot Quicksort Process作者机构：Department of Mathematies Faculty of Science Al Azhar University Cairo Egypt Department of Mathematics Faculty of Science Mansoura University Mansoura Egypt
出 版 物：《Open Journal of Modelling and Simulation》 (建模与仿真（英文）)
年 卷 期：2016年第4卷第1期
页 面：1-15页
学科分类：07[理学] 0701[理学-数学] 070101[理学-基础数学]
主 题：Randomized Quicksort Convergence Dual-Pivot Quicksort Process Running Time Analysis
摘 要：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.
维普期刊数据库