Quick sort is a divide-and-conquer sorting algorithm. To understand quick-sort, let us look at a high-level description of the algorithm.

  1. Divide: If the sequence S has 2 or more elements, select an element x from S to be your pivot. Any arbitrary element, like the last, will do. Remove all the elements of S and divide them into 3 sequences:

    1. L, which holds S’s elements less than x
    2. E, which holds S’s elements equal to x
    3. G, which holds S’s elements greater than x
  2. Recurse: Recursively sort L and G
  3. Conquer: Finally, to put elements back into S in order, first insert the elements of L, then those of E, and then those of G.

Idea of Quick Sort

  1. Select: pick a pivot element ‘x’
  2. Divide: rearrange elements so that the ‘x’ goes to its final position E
  3. Recurse and Conquer: recursively sort

Illustration of the Divide Step

Let us choose the last element of the array, 50, as the pivot element. Our aim is to place this element in its final position. In other words, all elements less than or equal to the pivot will be to its left and all elements greater than or equal to the pivot will be to its right.

Quick sort paritioning

We will take the help of two variables: l and r. l scans the sequence from the left, and r from the right.

l is successively incremented until it reaches an element greater than or equal to the pivot.

r is successively decremented until it reaches an element that is less than the pivot.

Now, l and r both point to elements on the wrong sides, so a swap is performed. The swap is performed only if l < r.

These steps are repeated until l >= r. Now, we swap the pivot element with the element at position l. This concludes the partitioning procedure.
Quick sort partioning

Quick sort partioning

Algorithm

quicksort(a, l, r)

Begin
if(l<r) then
splitarray(a,l,r,loc) //partition the array
quicksort(a,l,loc-1) //recursively sort left sub array
quicksort(a,loc+1,r) //recursively sort right sub array
endif
end

Analysis of Quick Sort

Finding the location of the element that splits the array into two sections is an O(n) operation, because every element in the array is compared to the pivot element.

After the division, each section is examined separately.

If the array is split approximately in half (an optimistic assumption), then there will be log2n splits.

Therefore, the total comparisons will be:
f(n) = n*log2n = O(nlog2n)

Complete Program

.cf { font-family: Lucida Console; font-size: 9pt; color: black; background: white; } .cl { margin: 0px; } .cb1 { color: green; } .cb2 { color: blue; } .cb3 { color: maroon; }

/**
 * Quick Sort
 * http://www.byteguide.com
 */
 
#include <stdio.h>
 
void quicksort(int [], int );
 
int main()
{
    int a[50], n, i;
    printf("How many elements do you want to create the array with?"
        "(max 50): ");
    scanf("%d", &n);
    fflush(stdout);
    puts("Enter the array elements");
    for (i=0; i<n; i++)
        scanf("%d", &a[i]);
    quicksort(a, n);
    puts("--------Sorted Array--------");
    for (i=0; i<n; i++)
        printf("%dn", a[i]);
    printf("n");
 
    return 0;
}
 
void recursivequicksort(int [], int, int);
void quicksort(int arr[], int n)
{
    recursivequicksort(arr, 0, n-1);
}
 
 
int partition(int [], int, int);
void recursivequicksort(int arr[], int low, int high)
{
    int pivotpos; /*position of the pivot after partitioning*/
    if (low<high)
    {
        pivotpos = partition(arr, low, high);
        recursivequicksort(arr, low, pivotpos-1);
        recursivequicksort(arr, pivotpos+1, high);
    }
}
 
void swap(int [], int, int);
int partition(int arr[], int low, int high)
{
    int down = low, up = high;
    int pivot = arr[high];
    while (down<up)
    {
        while(arr[down]<pivot && down<up)
            down++;
        while (arr[up]>=pivot)
            up--;
        if (down<up)
            swap(arr, down, up);
    }
    arr[high] = arr[down];
  arr[down] = pivot;
    return down;
}
 
void swap(int arr[], int i, int j)
{
    int temp;
    temp = arr[i];
    arr[i] = arr[j];
    arr[j]=temp;
}

Output

How many elements do you want to create the array with?(max 50): 6
Enter the array elements
3
67
85
89
56
44
 ——–Sorted Array——–
3
44
56
67
85
89