Quick Sort
Quick sort is a very popular sorting method. This sort name comes from the fact that quick sort can sort a list of data elements significantly faster than any of the common sorting algorithms. This sorting uses a strategy called divide and conquer. It is based on the principle that is faster and easier to sort two small arrays than one larger one.
The sequence of steps required to perform a quick sort operation on a set of elements of the array are as follows.
- A pivot item near the middle of the array is chosen. Let it be x.
- Now scan the array from left to right until some element e.g., ai>x is encountered.
- Now scan the array from right to left until some element e.g.,aj<x is encountered.
- Now exchange the items ai and aj.
- Again repeat steps 2 to 4 until the scan operation meets somewhere in the middle of the array.
Quick sort is also called partition exchange sort and it was invented by C.A.R. Hoare. The average execution time of quick sort is O(n(log2n)2) and this sort is good for large sorting jobs.
Pictorial Representation
Quick Sort Algorithm
1. If n < = 1, then return.
2. Pick any element V in a[]. This is called the pivot.
3. Rearrange elements of the array by moving all elements xi > V right of V and all elements xi < = V left of V. If the place of the V after re-arrangement is j, all elements with value less than V, appear in a[0], a[1] . . . . a[j – 1] and all those with value greater than V appear in a[j + 1] . . . . a[n – 1].
4. Apply quick sort recursively to a[0] . . . . a[j – 1] and to a[j + 1] . . . . a[n – 1].
Program for Quick Sort
#include <stdio.h>
void quick_sort(int[], int, int);
int partition(int[], int, int);
int main()
{
int a[50], n, i;
printf("How many elements?");
scanf("%d", & n);
printf("\nEnter array elements:");
for (i = 0; i < n; i++)
{
scanf("%d", & a[i]);
}
quick_sort(a, 0, n - 1);
printf("\nArray after sorting:");
for (i = 0; i < n; i++)
{
printf("%d ", a[i]);
}
return 0;
}
void quick_sort(int a[], int l, int u)
{
int j;
if (l < u)
{
j = partition(a, l, u);
quick_sort(a, l, j - 1);
quick_sort(a, j + 1, u);
}
}
int partition(int a[], int l, int u)
{
int v, i, j, temp;
v = a[l];
i = l;
j = u + 1;
do
{
do
{
i++;
}
while (a[i] < v && i <= u);
do
{
j--;
}
while (v < a[j]);
if (i < j)
{
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
while (i < j);
a[l] = a[j];
a[j] = v;
return (j);
}
The complexity of the quick sort algorithm is given in the following table.
Algorithm | Worst case | Average case | Best case |
Quick sort | O(n)2 | log2n | log2n |