C Quicksort Algorithm

Summary: this tutorial will teach you 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 sublists: a low-elements sublist and a high-elements sublist, and then recursively sorts these sublists.

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 less than the pivot come before the pivot, whereas all elements 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 quicksort algorithm’s complexity in the worst case is O(n2), and in both the best and average cases, it is O(n log n), where n is the number of unsorted elements.

The following picture illustrates how the  quicksort algorithm sorts 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.