Quick sort

It is an algorithm of Divide & Conquer type.

Divide: Rearrange the elements and split arrays into two sub-arrays and an element in between search that each element in left sub array is less than or equal to the average element and each element in the right sub- array is larger than the middle element.

Conquer: Recursively, sort two sub arrays.

Combine: Combine the already sorted array.

Algorithm:

QUICKSORT (array A, int m, int n) 
 1 if (n > m) 
 2 then 
 3 i ← a random index from [m,n] 
 4 swap A [i] with A[m] 
 5 o ← PARTITION (A, m, n) 
 6 QUICKSORT (A, m, o - 1)
 7 QUICKSORT (A, o + 1, n)

Partition Algorithm:

Partition algorithm rearranges the sub arrays in a place.

PARTITION (array A, int m, int n) 
 1 x ← A[m] 
 2 o ← m 
 3 for p ← m + 1 to n
 4 do if (A[p] < x) 
 5 then o ← o + 1 
 6 swap A[o] with A[p]
 7 swap A[m] with A[o] 
 8 return o

Figure: shows the execution trace partition algorithm

Example of Quick Sort:

  44	33	11	55	77	90	40	60	99	22	88	

Let 44 be the Pivot element and scanning done from right to left

Comparing 44 to the right-side elements, and if right-side elements are smaller than 44, then swap it. As 22 is smaller than 44 so swap them.

  22	33	11	55	77	90	40	60	99	44	88	

Now comparing 44 to the left side element and the element must be greater than 44 then swap them. As 55 are greater than 44 so swap them.

22	33	11	44	77	90	40	60	99	55	88

Recursively, repeating steps 1 & steps 2 until we get two lists one left from pivot element 44 & one right from pivot element.

22	33	11	40	77	90	44	60	99	55	88

Swap with 77:

22	33	11	40	44	90	77	60	99	55	88

Now, the element on the right side and left side are greater than and smaller than 44 respectively.

Now we get two sorted lists:

And these sublists are sorted under the same process as above done.

These two sorted sublists side by side.

Merging Sublists:

                          SORTED LISTS

Worst Case Analysis: It is the case when items are already in sorted form and we try to sort them again. This will takes lots of time and space.

Equation:

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

T (1) is time taken by pivot element.

T (n-1) is time taken by remaining element except for pivot element.

N: the number of comparisons required to identify the exact position of itself (every element)

If we compare first element pivot with other, then there will be 5 comparisons.

It means there will be n comparisons if there are n items.

Relational Formula for Worst Case:

Note: for making T (n-4) as T (1) we will put (n-1) in place of '4' and if
We put (n-1) in place of 4 then we have to put (n-2) in place of 3 and (n-3)
In place of 2 and so on.

T(n)=(n-1) T(1) + T(n-(n-1))+(n-(n-2))+(n-(n-3))+(n-(n-4))+n
T (n) = (n-1) T (1) + T (1) + 2 + 3 + 4+............n
T (n) = (n-1) T (1) +T (1) +2+3+4+...........+n+1-1

[Adding 1 and subtracting 1 for making AP series]

T (n) = (n-1) T (1) +T (1) +1+2+3+4+........ + n-1
T (n) = (n-1) T (1) +T (1) + -1

Stopping Condition: T (1) =0

Because at last there is only one element left and no comparison is required.

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

Worst Case Complexity of Quick Sort is T (n) =O (n²)

Randomized Quick Sort [Average Case]:

Generally, we assume the first element of the list as the pivot element. In an average Case, the number of chances to get a pivot element is equal to the number of items.

Let total time taken =T (n)
For eg: In a given list
   p 1,   p 2,    p 3,    p 4............pn
  If p 1 is the pivot list then we have 2 lists.
     I.e. T (0) and T (n-1)
  If p2 is the pivot list then we have 2 lists.
        I.e. T (1) and T (n-2)
   p 1,   p 2,    p 3,    p 4............pn
 If p3 is the pivot list then we have 2 lists.
  I.e. T (2) and T (n-3)
    p 1,   p 2,    p 3,    p 4............p n

So in general if we take the Kth element to be the pivot element.

Then,

Pivot element will do n comparison and we are doing average case so,

So Relational Formula for Randomized Quick Sort is:

    = n+1 +(T(0)+T(1)+T(2)+...T(n-1)+T(n-2)+T(n-3)+...T(0))

    = n+1 +x2 (T(0)+T(1)+T(2)+...T(n-2)+T(n-1))

n T (n) = n (n+1) +2  (T(0)+T(1)+T(2)+...T(n-1)........eq 1

Put n=n-1 in eq 1

(n -1) T (n-1) = (n-1) n+2 (T(0)+T(1)+T(2)+...T(n-2)......eq2

From eq1 and eq 2

n T (n) - (n-1) T (n-1)= n(n+1)-n(n-1)+2 (T(0)+T(1)+T(2)+?T(n-2)+T(n-1))-2(T(0)+T(1)+T(2)+...T(n-2))
n T(n)- (n-1) T(n-1)= n[n+1-n+1]+2T(n-1)
n T(n)=[2+(n-1)]T(n-1)+2n
n T(n)= n+1 T(n-1)+2n

Put n=n-1 in eq 3

Put 4 eq in 3 eq

Put n=n-2 in eq 3

Put 6 eq in 5 eq

Put n=n-3 in eq 3

Put 8 eq in 7 eq

From 3eq, 5eq, 7eq, 9 eq we get

From 10 eq

Multiply and divide the last term by 2

Is the average case complexity of quick sort for sorting n elements.

3. Quick Sort [Best Case]: In any sorting, best case is the only case in which we don't make any comparison between elements that is only done when we have only one element to sort.