文章基本信息

标题：On the Convergence of the Dual-Pivot Quicksort Process
本地全文：下载
作者：Mahmoud Ragab ; Beih El-Sayed El-Desouky ; Nora Nader 等
期刊名称：Open Journal of Modelling and Simulation
印刷版ISSN：2327-4018
电子版ISSN：2327-4026
出版年度：2016
卷号：04
期号：01
页码：1-15
DOI：10.4236/ojmsi.2016.41001
语种：English
出版社：Scientific Research Publishing
摘要：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