Quick Sort

It is a popular sorting method based on the divide-and-conquer approach. Unlike merge sort, where the division is always in the middle, in quicksort the division can take place at any position.

In quicksort, the division depends on the value of an element. Partition is the situation in quicksort where, if we achieve partition about some index s, then:

a[s] is the pivot element.
All elements preceding a[s] are <= a[s].
All elements following a[s] are >= a[s].

Clearly, after partition, a[s] takes its final position in the sorted array. Partition is the most important procedure of quicksort. After achieving partition about s, a[s] takes its final position, leaving two unsorted subarrays:

the part preceding a[s], and
the part following a[s].

In quicksort, the pivot (partition element) can be at any location, depending on the value of the key element. The simplest strategy is to select the first element as the pivot.

Worst Case of Quick Sort

For input size N, when elements are in strictly increasing order, after the first comparison we achieve partition at the first position, replacing the first element by itself. This leaves us with a subarray of size N – 1.

Again, after the next comparison, the first element of this subarray replaces itself, leaving a subarray of size N – 2.

This process continues. Finally, quicksort will sort the subarray of size 2, and after that the array will be completely sorted.

Thus, in the worst case, quicksort performs:

$By Comutative low (a + b) = (b + a)

\boxed{C_{w}(n)=1+2+3+\cdot\cdot\cdot+(n+1)-3\quad\left(1\right)}

AP Series:

S_{n}=a+(a+d)+(a+2d)+(a+3d)+\dots+(a+(n-1)d)

= common difference
= first term of the series
= term of the series

Sum of first n term of an ap series

S_{n}=\frac{n}{2}\left(2a+(n-1)d\right)

we have

C_{w}(n)=1+2+3+\dots+(n+1)-3

= 1
= 1
term =

C_{w}(n)=S_{n}=\frac{(n+1)}{2}\left(2\cdot1+(n+1-1)\cdot1\right)-3

C_w(n) = \frac{(n+1) \cdot (n+2)}{2} - 3

C_w(n) = \frac{n^2 + 3n + 2 - 6}{2}

C_w(n) = \tfrac{1}{2}\left(n^2 + 3n - 4\right)

\frac{T(n)}{g(n)}=c\quad\text{for some constant }c>0

T(n)g(n)$ grow at the same rate.

So,

T(n)\in\Theta(g\left(n)\right)

\lim_{n\to\infty}\frac{C_{w}(n)}{n^2}

\lim_{n \to \infty} \frac{\frac{1}{2}(n^2 + 3n - 4)}{n^2}

\frac{1}{2} \lim_{n \to \infty} \left(1 + \frac{3}{n} - \frac{4}{n^2}\right)

\frac{1}{2} \left(1 + 0 - 0\right)

\boxed{C_w(n) = \tfrac{1}{2}\left(n^2 + 3n - 4\right) \quad \in \ \Theta(n^2)}

Best Case of Quick Sort

The best case of quicksort occurs when we achieve partition exactly in the middle of the subarray.

For an array , partitioning happens at its mid position. After partition, the array is divided into two equal parts:

of size if is odd (), or
of size if is even ().

This means that in the very first position, the pivot divides the array into two equal halves.

If is the time taken by quicksort to sort an array of size , then from recurrence, we have:

C_{b}(n)=C_{b}\!\left(\tfrac{n}{2}\right)+C_{b}\!\left(\tfrac{n}{2}\right)+O(n),\quad n>1

on solving

Cb(n)\ \ \in\ \ O(n\log_2{n})

Average Case of Quick Sort

The possibility of getting a partition at any position is , where .

If is the average time to sort an array of size , then the recurrence is:

C_{A}(n)=\frac{1}{n}\sum_{k=1}^{n}\Big((n+1)+C_{A}(k-1)+C_{A}(n-k)\Big)\quad eq:(1)

C_{A}(0)=0C_{A}(1)=0

= Cost of partitoning
= Cost of left Subarray.
= Cost of right Subarray.

Notice the Symmetry of Double Counting

Notice that for each pivot , the recurrence adds . Because of symmetry:

\begin{aligned}nC_{A}(n) & =(n+1)\cdot n\Big[C_{A}(0)+C_{A}(n-1)\quad & (k=1)\\ & +C_{A}(1)+C_{A}(n-2)\quad & (k=2)\\ & +C_{A}(2)+C_{A}(n-3)\quad & (k=3)\\ & \;\;\;\vdots & \\ & +C_{A}(n-3)+C_{A}(2)\quad & (k=n-2)\\ & +C_{A}(n-2)+C_{A}(1)\quad & (k=n-1)\\ & +C_{A}(n-1)+C_{A}(0)\quad & (k=n)\Big]\end{aligned}

k=1n$ with two terms each, we can just sum over all subarray sizes once and multiply by 2.

\begin{aligned}n\,C_{A}(n) & =n\cdot(n+1)+2\,\Big[C_{A}(0)\quad & (k=1)\\ & +C_{A}(1)\quad & (k=2)\\ & +C_{A}(2)\quad & (k=3)\\ & \;\;\;\vdots & \\ & +C_{A}(n-3)\quad & (k=n-2)\\ & +C_{A}(n-2)\quad & (k=n-1)\\ & +C_{A}(n-1)\quad & (k=n)\Big]\end{aligned}

From Recurrance relation (2) we have

\boxed{(n-1)C_A(n-1) = n(n-1) + 2\big(C_A(0) + C_A(1) + \dots+ C_A(n-2)\big)}\quad eq:(3)

We have:

Eq. (2):

nC_{A}(n)=n(n+1)+2\big(C_{A}(0)+C_{A}(1)+\dots+C_{A}(n-1)\big)

Eq. (3):

(n-1)C_{A}(n-1)=n(n-1)+2\big(C_{A}(0)+C_{A}(1)+\dots+C_{A}(n-2)\big)

Step 1: Subtract LHS

nC_{A}(n)-(n-1)C_{A}(n-1)

Step 2: Subtract RHS

\Big(n(n+1)-n(n-1)\Big)+2\Big[(C_{A}(0)+\dots+C_{A}(n-1))-(C_{A}(0)+\dots+C_{A}(n-2))\Big]

Simplify each part:

The summations cancel except the last term:

(C_{A}(0)+\cdot\cdot\cdot+C_{A}(n-1))-(C_{A}(0)+\dots+C_{A}(n-2))=C_{A}(n-1)

So the RHS =

2n+2C_{A}(n-1)

Step 3: Final Relation

nC_{A}(n)-(n-1)C_{A}(n-1)=2n+2C_{A}(n-1)

nC_{A}(n)=2n+2C_{A}(n-1)+(n-1)C_{A}(n-1)

nC_{A}(n)=2n+C_{A}(n-1)\cdot(2+n-1)

\boxed{nC_A(n) = 2n + C_A(n-1) \cdot (n+1) }

Multiply on both side

\frac{C_A(n)}{(n+1)}=\frac{2}{n+1}+\frac{C_A(n-1)}{n}\quad eq:(4)

Put in this

\frac{C_A(n-1)}{n}=\frac{C_A(n-2)}{(n-1)}+\frac{2}{n}