QuickSort Algorithm

Left
Middle(only one element)
Right

Procedure QUICKSORT (A,p,r)
 1 if p < r
 2     then q ← PARTITION(A,p,r)
 3             QUICKSORT (A,p,q-1)
 4             QUICKSORT (A,q+1,r)

Partition Algorithm 01

Procedure PARTITION(A,p,r)
1    x ←  A[p]
2    i ←  p -1
3    j ← r +1 
4    while  TRUE
5           do repeat  j ←  j  - 1
6                    until  A[j]   ≤ x 
7                 repeat   i  ←  i + 1  
8                    until   A[i] ≥ x
9                 if    i < j	
10                    then   exchange A[i] ↔A[j]
11                   else return j

Partition Algorithm 02

PARTITION(A, p, r) 

1 x ← A[r] 
2 i ← p - 1 
3       for j ← p to r - 1 
4           do if A[j] ≤ x 
5                    then i ← i + 1 
6                      exchange A[i] ↔ A[j] 
7      exchange A[i + 1] ↔ A[r] 
8   return i + 1

Analysis of Quick sort
The running time of quick sort depends on the partitioning of the sub arrays:
(a) Worst case partitioning(Unbalanced)



 

nOccurs when the sub arrays are completely unbalanced.

nHave 0 elements in one sub array and n − 1 elements in the other sub array.

nTime taken for partitioning is  Q(n) and T(0)= Q(1).

 

nTherefore Recurrence Equation is

T(n) = T(n-1) +T(0)+ Q(n)