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.