Quick Sort (Part- 4)

REFERENCE : PANIMALAR ENGINEERING COLLEGE NOTES
Quick Sort:
Quick sort is one of the most efficient internal sorting technique. It possess a very good average behavior among all the sorting techniques. It is also called as partitioning sort which uses divide and conquer techniques.
                The quick sort works by partitioning the array A[1], A[2]. . . A[N] by picking some key value in the array as a pivot element.Pivot element is used to rearrange the elements in a array. Pivot element can be the first element of an array and the rest of the elements are moved so that elements on left side of the pivot are lesser than the pivot, whereas those on the right sie are greater than the pivot. Now the pivot element is placed in the correct position. Now the quick sort procedure is applied for left array and right array in a recursive manner.

void qsort (int A[ ] , int left, int right)
{
int i,j, temp, pivot;

if(left{
pivot = left;
i = left + 1;
j = right;
while(i{
while(A[pivot]>=A[j])
i++;
while(A[pivot]j--;
if(i{
temp=A[j];
A[i]=A[j];
A[j]=temp;
}
}
temp = A[pivot];
A[pivot] = A[j];
A[j]=temp;
qsort(A,left,j-1);
qsort(A,j+1,right);
}
}

Example: Consider an unsorted array as follows40         20         70          14          60           61            97          30Here pivot = 40

40      20      70      14      60      61      97      30

40      20      70      14      60      61      97      30

40      20      30      14      60      61      97      70

Pass 1:

14      20      30      40      60      61      97      70

Now the pivot element reached its correct position. The elements lesser than pivot {14     20       30} is considered as left sub array. The elements than the pivot { 60     61     97     70} is considered as right sub array. Then the Qsort procedure is applied recursively for both these arrays.

Analysis of Quick Sort

Worst Case Analysis                 - O(N²)

Best Case Analysis                   - O (N log N)

Average Case Analysis              - O (N log N)

Advantages of Quick Sort

It is faster than other O(N log N) algorithms.

It has better cache performance.

Limitations

It requires extra memory space.

It requires more processing time.