Everything You Always Wanted to Know about Quicksort, but Were Afraid to Ask.pdf

Algorithms Seminar 2001–2002, F. Chyzak (ed.), INRIA, (2003), pp. 57–62. Available online at the URL http://algo.inria.fr/seminars/. Everything You Always Wanted to Know about Quicksort, but Were Afraid to Ask Marianne Durand Projet Algorithmes, Inria Rocquencourt (France) November 5, 2001 Summary by Michel Nguy??en-Th′?e Abstract The algorithm Quicksort was invented by Hoare in 1960. Numerous improvements have been suggested since then, like optimization of the choice of the pivot or simultaneous use of several pivots or also hybrid methods. Different parameters like the cost of comparisons, the size or the height of the associated binary search tree have been studied for Quicksort and its variants. We present here the principal methods used to get the mean, the variance, and the nature or at least a few properties of the limit laws of these parameters. 1. Description of the Algorithm and of a Few Variants 1.1. Quicksort. The procedure Quicksort takes as arguments an array A of n elements and two integers First and Last representing indices of elements of the array. The algorithm runs as follows: if First Last then: 1. Choose a pivot in the array (e.g., A[First]). 2. Partition the elements in the subarray A[First] . . . A[Last] so that the pivot value is in place (let PivotIndex be its position then). 3. Apply Quicksort to the first subarray A[First] . . . A[PivotIndex? 1]. 4. Apply Quicksort to the second subarray A[PivotIndex + 1] . . . A[Last]. 1.2. Variants. In step 1, the pivot is chosen in a fixed manner. It is possible to use a strategy to choose the pivot to improve the efficiency of the algorithm. By choosing the pivot randomly, we can wipe out the possible bias of the data we want to sort. The pivot is all the more efficient if it cuts the array in two arrays of similar size. With this aim in view, the Quicksort with median of 2t+ 1 consists in picking out 2t + 1 elements randomly in the array to sort, where t is a fixed integer, and to choose as pivot t