Question

Show in a formal mathematical proof, theoretical analysis, substitution method, an even split of an array into two subarrays which answers in the best performance of quicksort algorithm "appraised with respect to the running time". coding or empirical investigation are not needed.

Answer 1

Quicksort is another sorting algorithm which uses Divide and Conquer for its implementation. Quicksort is also the practical choice of algorithm for sorting because of its good performance in the average case which is Θ(nlgn).

Partition in Quicksort

The first step of doing a partition is choosing a pivot. We are going to always select the last element of the array as the pivot in our algorithm and focus mainly on the concepts behind the Quicksort. However, there can be different ways of choosing the pivot like the median of the elements, the first element of the array, random element, etc.

After choosing the pivot, our next task is to place all the elements smaller than the pivot on one side and all the elements larger than the pivot on another side. We will do this by iterating over the array and on finding an element larger than the pivot, doing nothing. This will start making a cluster of elements larger than the pivot.

Analysis of Quicksort

We know that Quicksort takes Θ(n2) time in the worst case and Θ(nlgn)

in the best case.   Now, the total running time of the QUICKSORT function is going to be the summation of the time taken by the PARTITION(A, start, end) and two recursive calls to itself. The comparison (if start < end) is going to take a constant amount of time and thus, we are ignoring it.

the PARTITION function is a linear (i.e., Θ(n)

) one because there is just one loop which is iterating over the entire array (of size n) and all the other statements are constant time taking processes.

Let's take a case when the partition is always balanced i.e., every time, each of the two halves separated by the pivot has no more than n2

elements. It means that one of the halves has ⌊n2⌋ and another has ⌈n2⌉−1 elements. For example, if n is 5, then one half has ⌊52⌋=2 elements and another has ⌈52⌉−1=2

elements and thus, a total of 2+2+1(pivot) = 5 elements.

In that case, QUICKSORT(A, start, q-1) and QUICKSORT(A, q+1, end) will take T(n2)

each and the PARTITION function is going to take Θ(n) time.

Now, let's take the case when the partition is completely unbalanced every time i.e., each time, one half is of the size n−1 and other of size 0

.

In this case, the total running time would be:

T(n)=T(n−1)+T(0)+Θ(n)

=>T(n)=T(n−1)+Θ(n)

We can solve this recurrence equation by iteration method i.e., putting replacing T(n−1)

with T(n−2)+Θ(n) and again T(n−2) with T(n−2)+Θ(n)

and so on.

T(n)=T(n−1)+Θ(n)

Replacing T(n−1) with (T(n−2)+Θ(n)), =>T(n)=T(n−2)+Θ(n)+Θ(n) Replacing T(n−2) with (T(n−3)+Θ(n)), =>T(n)=T(n−3)+Θ(n)+Θ(n)+Θ(n) Similarly, T(n)=T(n−i)+i∗Θ(n)

Thus, in the base case, when there will be an only single element, the running time will become T(n)=T(0)+n∗Θ(n)

which is equal to Θ(n2)

So, we have seen that Quicksort takes Θ(nlgn)

time in the balanced partition and Θ(n2) time in the unbalanced one.

The choice of a pivot is most critical:
The wrong choice may lead to the worst-case quadratic time complexity.
A good choice equalises both sublists in size and leads to
linearithmic (\n log n") time complexity.
However, quicksort is fast on the \randomly scattered" pivots.