Analysis of the Multi-Pivot Quicksort Process

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

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

DOI: 10.4236/ojmsi.2017.51004                

Abstract

In this paper, we study a new version from Dual-pivot Quicksort algorithm when we have some other number of pivots. Hence, we discuss the idea of picking pivots  by random way and splitting the list simultaneously according to these. The modified version generalizes these results for multi process. We show that the average number of swaps done by Multi-pivot Quicksort process and we present a special case. Moreover, we obtain a relationship between the average number of swaps of Multi-pivot Quicksort and Stirling numbers of the first kind.

Keywords

Quicksort, Convergence, Multi-Pivot Quicksort Process, Stirling Number of the First Kind

1. Introduction

Quicksort studied in many books such as [1] [2] and [3] . It is an exhaustively anatomize sorting algorithm and following the idea of divide-and-conquer on an input consisting of items [4] . Quicksort used a pivot item to divide its input items into two partitions; the items in one sublist seem diminutive or identically tantamount to the pivot; the items in the other sublist seem more sizably voluminous than or equipollent to the pivot, after then it uses recursion to order these sublists. It is prominent that the input consists of items with different keys in arbitrary order and the pivot is picked by just picking an item, and then on average Quicksort utilizes comparisons between items from the input. The Partial Quicksort algorithm analyzed by Ragab [5] [6] and [7] depends on the idea of the standard Quicksort. It uses a smart strategy to find the smallest elements out of distinct elements and sort them. Yaroslavskiy declared in 2009 that he had made some improvements for the Quicksort algorithm, the demand being drawn by experiments.

Yaroslavskiy’s algorithm replaced the new standard Quicksort algorithm in Oracle’s Java 7 runtime library. This algorithm uses two items as pivots to divide the items. If two pivots and such that are used, the splitting step sublists the remaining items into three sublists, items more minute than or equipollent to, items between and, and items more sizably voluminous than or equipollent to. Recursion is then applied to the three sublists. It came as a surprise that two pivots should avail, since in his thesis [8] Sedgewick had introduced and explained a Dual- pivot technique inferior to classical Quicksort. Hence, Hennequin in his thesis studied the general technique of using pivot items [2] .

We analyze the limiting distribution of the number of swaps needed by the duality process is proposed. It is known to be the unique fixed point of a certain distributional transformation with zero mean and finite variance. Depending on the results of [1] and [9] , we analyze the Multi-pivot Quicksort when we selected pivots and we study the relationship with Striling numbers of the first kind.

2. Multi -Pivot Quicksort

Later, many researchers has received the interest of the visualization of multi-pivot Quicksort in accordance with Yaroslavskiy proposed the duality pivot process which outperforms standard Quicksort by Java JVM. After that, this algorithm has been explained in terms of comparisons and swaps by Wild and Nebel [10] .

A normal expansion of duality process would be to have some other number of pivots. Hence, we cogitation the approximation of pick pivots by random way and splitting the list simultaneously according to these. let a random permutation of the list be given to be ordered using this variant, with all the substitution. The rightmost item are picked as pivots are compared to each other and interchange, if they are out of order.

There are items are swaps to the pivots and the list is splitted to sublists. The partition step can be worked as follows. We compare the leftmost item to pivot which chosen by random way; if this pivot is bigger than it, it is compared with another pivot which was smaller than the first pivot. Otherwise it is swaped with a bigger pivot (to the right) and after a series of number of swaps are inserted to its place between any two pivots, or to the left of the smallest pivot or to the right of the biggest pivot. We continue with the same technique, until all items are examined.

Each item of the items swaps with the pivots by binary tree, first each item is swaps with the median of the sorted list of the pivots. If it is compared with the first element, otherwise is compared with the third element and after a collection of swaps is inserted to its placement.

For the pervious process, there are sublists. If we let that the input is a random permutation of.

We assume that be an integer. The method “-pivot quicksort” performs as follows:

As long as then sort the input directly. When, order the first items such that and set . In the splitting step, the remaining items are divided to sets where an item belongs to set as long as. The sets are then ordered recursively. Assume that be fixed. As for duality Quicksort process, if we assume that and give the random variables that count the swaps required to sort items when we select pivot items, uniformly selected from the list and partitioning respectively. The total number of swaps needed by Multi-pivot Quicksort sorting inputs given by

(1)

where random variable that count the number of swaps made for sort the items smaller than first pivot denote the number of swaps need to order the items between first pivot and the second pivot. denote the number of swaps need to order the items between pivot and the pivot. The random variables, and have the same distribution and independent of and means the equality in distribution.

The average number of swaps done by the multi algorithm applied to an list of items by -pivot Quicksort given by the following recurrence

(2)

where refers to the pivots in increasing order, see [11] and [12] .

Let be the expected value of a “toll function” during the

first recursive call, where and are constants and denotes

the average number of swaps for ordering the sublist of items less than by the Multi-Pivot Quicksort on pivots to simplify the relation by noting that the pivots are selected by the random way and the sums are equal,

By collecting terms with a common factor, when. Fix There are methods of picking with.

(3)

Multiplying both sides by, the recurrence relation becomes

multiplying by and summing over., hence we get the generating function for the average number of swaps [10] . Let and consider the generating func-

tion

(4)

We find that

Such that gives the k-th order derivative of In the right-hand side of Equation (4), the first sum becomes

.

The recurrence becomes as follows

(5)

In the right -hand side of Equation (5). The first sum becomes in this form because it may be easily explained by mathematical induction that the k-th order derivative of

is

The recurrence is converted to the following differential equation [13] :

(6)

Multiplying by, the previous Equation (6) is transformed to

This differential equation is a Cauchy-Euler equation [14] . We change variables , it is

(7)

By using the differential operator to solve the previous differential Equation (7) which is defined by

and using the mathematical induction we find that at

and

We find

the relation holds at. We assume the relation holds at

at we find

So, it is easy to find the relation is satisfied for all values of

When we apply the operator, our relation seems in the form

(8)

where is called as the initial polynomial and is given as follows, see [15] ,

where with, denotes the falling factorial. If we use the fundamental theorem of algebra which proposed that a polynomial of degree has complex roots with multiplicities. Notice that −2 is constantly a simple root because,

And we get

Setting and the residual roots be, see [16] . Our polynomial be in the form

This differential equation can be written as

(9)

where to solve our differential equation, we assume that there are two functions and where

Then

By using the property of linearity of differential operator

if we apply times the solution, we get

(10)

(11)

where and are constants of integration. Note that

Therefore, to evaluate, we find

(12)

(13)

Moreover

Combining both solutions,

(14)

such that. To solve this system of of equations, we should calculate the constants of integration

In terms of series;

(15)

The third sum of Equation (15) collects to the solution a stationary contribution. Furthermore, the root when is even, participates a constant and the root, collects, with. Eliciting the coefficients, the average number of swaps for Multi-pivot Quicksort is

(16)

The number of methods to permute a list of items into cycles counted by the Stirling numbers of the first kind see [17] .

We show the relation between the number of swaps done by the multi Quicksort process and Sirling number of the first kind. Form Equation (17) we assume that

and consider the generating function

(17)

The relation is converted to a k-th order differential equation

This differential equation is a Cauchy-Euler equation. We use the deferential operator for the solution of the differential equation. It is defined as follows

also, by induction

applying the operator,our equation becomes

where is falling factorial, see [18] .

where is Stirling numbers of the first kind, see [19] . we use the relation

hence

by equality the coefficients we obtain

3. Quicksort

In this section we show the average number of swaps needed by the Quicksort is a particular case form the public case of the multi-pivot Quicksort [20] . For

(18)

where give the random variables which counting the number of swaps needed for splitting the list of items, such that the classical algorithm is applied to an list of different items [5] . We find that such that if, the following recurrence holds. We find the average number of swaps done by the Quicksort from Equation (2) we find at the equation becomes

(19)

Assume that if we need to sort list of of different items, where their positions in the list are counted from left to right by [6] . First, the item at position 1 compared with the pivot. The number of items which are bigger than pivot and were animated during split operation is

Subsequently, we consider as well that pivots are uniformly picked and noticing that we have to number the final swap with the pivot at the end of split operation [21] , we get

So, we find the toll function given by

We find, So the recurrence becomes

(20)

(21)

We solve this recurrence relation by transforming into a differential equation. First multiply both sides by

Let

multiplying by and summing over, so as to get the generating function for the average number of swaps consider the generating function

(22)

Multiplying by, the differential equation is simplified to

We can solve this differential equation using basic principles

(23)

This differential equation is a Cauchy-Euler equation [22] . We change variables, it is

we use the differential operator to solve the differential equation which defined as follows

applying the operator, our equation becomes

and applying the pervious technique we find the solution of the differential equation given by

(24)

where is constant of integration. In terms of series

(25)

Extracting the coefficients, the expected number of swaps for Multi-pivot Quicksort is

(26)

4. Conclusion

We study a new version from Dual-pivot Quicksort algorithm when we have some other number of pivots. Hence, we discuss the idea of picking pivots by random way and splitting the list simultaneously according to these. Moreover, we derive a generalization of this result for multi process. We show that the average number of swaps done by Multi-pivot Quicksort process and we present a special case. Furthermore, we present the relationship between the average number of swaps of Multi-pivot Quicksort and Stirling numbers of the first kind.

Acknowledgements

We thank the Editor and the referee for their comments.

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	Ragab, M., El-Desouky, B.S. and Nader, N. (2016) On the Convergence of the Dual-Pivot Quicksort Process. Open Journal of Modelling and Simulation, 4, 1-15. https://doi.org/10.4236/ojmsi.2016.41001
[2]	Hennequin, P. (1991) Analyse en moyenne d’algorithmes: Tri rapide et arbres de recherche. Ph.D. Thesis, Ecole Politechnique, Palaiseau.
[3]	Sedgewick, R. and Flajolet, P. (1996) An Introduction to the Analysis of Algorithms. Addison-Wesley, Longman, 1-492.
[4]	Hoare, C.A.R. (1962) Quicksort. Computer Journal, 5, 10-15. https://doi.org/10.1093/comjnl/5.1.10
[5]	Ragab, M. (2011) Partial Quicksort and Weighted Branching Processes. Ph.D. Thesis, 28-35.
[6]	Ragab, M. and Rosler, U. (2014) The Quicksort Process. Stochastic Processes and Their Applications, 2, 1036-1054. https://doi.org/10.1016/j.spa.2013.09.014
[7]	Ragab, M. (2015) On the Quicksort Algorithm and Its Related Process. Journal of Mathematical Modeling and Operations Research, 13-30.
[8]	Sedgewic, R.K. (1975) Quicksort. Ph.D. Thesis, Garland Publishing.
[9]	Iliopoulos, V. and Penman, D.P. (2012) Dual Pivot Quicksort. Discrete Mathematics, Algorithms and Applications, 4, Article ID: 1250041. https://doi.org/10.1142/S1793830912500413
[10]	Wild, S. and Nebel, M.E. (2012) Average Case Analysis of Java 7’s Dual Pivot Quicksort. Proceedings of the 20th European Symposium on Algorithms (ESA’12), 825-836. https://doi.org/10.1007/978-3-642-33090-2_71
[11]	Iliopoulos, V. (2013) Quicksorting on Multiple Pivots and a Vandermonde Matrix. Seminar in the Department of Mathematical Sciences, University of Essex, Colchester.
[12]	Iliopoulos, V. (2013) The Quicksort Algorithm and Related Topics. PhD Thesis, Department of Mathematical Sciences, University of Essex, Colchester. http://repository.essex.ac.uk/13266
[13]	Regnier, M. (1989) A Limiting Distribution for Quicksort. RAIRO—Theoretical Informatics and Application, 23, 335-343.
[14]	Roesler, U. (1992) A Fixed Point Theorem for Distributions. Stochastic Processes and Their Applications, 42, 195-214. https://doi.org/10.1016/0304-4149(92)90035-O
[15]	Rosler, U. (2001) On the Analysis of Stochastic Divide and Conquer Algorithms. Algorithmica, 29, 238-261. https://doi.org/10.1007/BF02679621
[16]	Fill, J.A. and Janson, S. (2001) Approximating the Limiting Quicksort Distribution. Random Structures Algorithms, 19, 376-406. https://doi.org/10.1002/rsa.10007
[17]	El-Desouky, B.S. and Cakic, N.P. (2011) Generalized Higher Order Stirling Numbers. Mathematical and Computer Modelling, 54, 2848-2857. https://doi.org/10.1016/j.mcm.2011.07.005
[18]	El-Desouky, B.S., Cakic, N.P. and Mansour, T. (2010) Modified Approach to Generalized Stirling Numbers via Differential Operators. Applied Mathematics Letters, 23, 115-120. https://doi.org/10.1016/j.aml.2009.08.018
[19]	El-Desouky, B.S, El-Bedwehy, N., Mustafa, A. and Menem, F. (2014) A Family of Generalized Stirling Numbers of the First Kind. Applied Mathematics, 5, 1573-1585. https://doi.org/10.4236/am.2014.510150
[20]	Fill, J.A. and Janson, S. (2004) The Number of Bit Comparisons Used by Quicksort: An Average-Case Analysis. ACM-SIAM Symposium on Discrete Algorithms, New Orleans, 11-13 January 2004, 300-307.
[21]	Knuth, D.E. (1973) The Art of Computer Programming, Volume III: Sorting and Searching. Addison-Wesley, Upper Saddle River.
[22]	El-Desouky, B.S. (2011) Generalized String Numbers of the First Kind: Modified Approach. Journal of Pure and Mathematics Advances and Applications, 5, 43-59.