C Quicksort Algorithm

Summary: in this tutorial, you will learn how to implement the quicksort algorithm in C.

Introduction to quicksort algorithm

The quicksort algorithm sorts an unordered list based on the divide and conquer strategy. It divides the unordered list into two sub-lists: low elements sub-list and high elements sub-list, and then recursively sort these sub-lists.

The following describes the quicksort algorithm steps:

1. Pick an element from the list, which is called a pivot.
2. Reorder the list with a rule that all elements which are less than the pivot come before the pivot, whereas all elements that are higher than the list come after the pivot. After partitioning the list, the pivot is in its position.
3. With the two sub-lists, apply the above steps recursively.

The complexity of the quicksort algorithm in the worst case is O(n²), in both best and average cases are O(n log n) where n is the number of unsorted elements.

The following picture illustrates how the  quicksort algorithm sort a list of integers:

The following animation illustrates how the quicksort algorithm works.

C quicksort algorithm implementation

The following is the quicksort program in C that uses the recursive function technique.

#include <stdio.h>
#include <stdlib.h>

void swap(int *x,int *y);
int choose_pivot(int i,int j );
void quicksort(int list[],int m,int n);
void display(int list[],const int n);

void main()
{
    const int SIZE = 10;
    int list[SIZE];

    int i = 0;

    /* generates random numbers and fill the list */
    for(i = 0; i < SIZE; i++ )
        list[i] = rand();

    printf("The list before sorting is:\n");
    display(list,SIZE);

    /* sort the list using quicksort algorithm */
    quicksort(list,0,SIZE-1);

    printf("The list after sorting:\n");
    display(list,SIZE);
}

void swap(int *x,int *y)
{
    int temp;
    temp = *x;
    *x = *y;
    *y = temp;
}

int choose_pivot(int i,int j )
{
    return((i+j) /2);
}

void quicksort(int list[],int m,int n)
{
    int key,i,j,k;
    if( m < n)
    {
        k = choose_pivot(m,n);
        swap(&list[m],&list[k]);
        key = list[m];
        i = m+1;
        j = n;
        while(i <= j)
        {
            while((i <= n) && (list[i] <= key))
                i++;
            while((j >= m) && (list[j] > key))
                j--;
            if( i < j)
                swap(&list[i],&list[j]);
        }
        /* swap two elements */
        swap(&list[m],&list[j]);

        /* recursively sort the lesser list */
        quicksort(list,m,j-1);
        quicksort(list,j+1,n);
    }
}
void display(int list[],const int n)
{
    int i;
    for(i=0; i<n; i++)
        printf("%d\t",list[i]);
}
Code language: C++ (cpp)

In this tutorial, we have introduced you to the quicksort algorithm and shown you how to implement quicksort in C.