Quick Sort Algorithm and Program in C

Introduction

QuickSort is a Divide and Conquer algorithm. Quick sort is a very efficient sorting algorithm. In Quick Sort an array is partitioned into two arrays one of which holds values smaller than the specified value, say pivot, based on which the partition is made and another array holds values greater than the pivot value.

There are many different ways of quickSort that pick pivot in different ways.

• Always pick first element as pivot.
• Always pick last element as pivot (implemented below)
• Pick a random element as pivot.
• Pick median as pivot.

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 x­i < = 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

#include<stdio.h>
#include<conio.h>

void QuickSort(int[], int, int);
int Partition(int[], int, int);

int main()
{
    int a[50], n, i;
    printf("Enter number of elements (n) = ");
    scanf("%d",&n);
    printf("\nEnter array elements:");

    for(i=0;i<n;i++)
        scanf("%d",&a[i]);

    QuickSort(a, 0, n-1);
    printf("\nArray after Quick Sorting:");

    for(i = 0; i < n; i++)
        printf("%d ",a[i]);

    getch();

    return 0;
}

void QuickSort(int a[], int l, int u)
{
    int j;
    if(l < u)
    {
        j = Partition(a, l, u);
        QuickSort(a, l, j-1);
        QuickSort(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);
}

Output