Skip to content
Search

Quicksort

lastmod 2025-12-10created 2016-06-096 edits

Quicksort is a sorting algorithm developed by Charles Antony Richard Hoare. It belongs to the comparison sorts, which sort using only comparisons with other elements.

Algorithm

Quicksort sorts a list using the divide and conquer method.

  1. Pick one element from the list. The element picked this way is called the pivot.
  2. Split the list in two around the pivot so that all elements smaller than the pivot come before it and all elements larger than the pivot come after it. Splitting the list in two this way is called partitioning. After partitioning, the pivot does not move anymore.
  3. Repeat this process recursively on the two smaller partitioned lists. The recursion repeats until the size of the list becomes 0 or 1.

Each time a recursive call runs, at least one element is placed in its final position, so this algorithm is guaranteed to terminate.

In-place partition algorithm

In imperative languages such as Pascal and C, it is mostly implemented using in-place partitioning like this. 

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

int len;

// Sorting in non decreasing order
void printArray(int arr[])
{
    for (int i = 0; i < len; i++)
        printf("%d ",arr[i]);
    printf("]\n");
}

void swap(int arr[], int k, int small)
{
    int temp;
    temp = arr[k];
    arr[k] = arr[small];
    arr[small] = temp;
}

int partition(int arr[],int i,int j)
{
    int pivot = arr[j];
    int small = i-1;
    for(int k = i;k<j;k++) {
        if(arr[k] <= pivot) {
            small++;
            swap(arr,k,small);
        }
    }

    swap(arr,j,small+1);
    printf("Pivot =  %d \n[",arr[small+1]);;
    printArray(arr);
    return small+1;
}

void quickSort(int arr[],int i,int j)
{
    if(i < j) {
        int pos = partition(arr,i,j);
        quickSort(arr,i,pos-1);
        quickSort(arr,pos+1,j);
    }
}

int main()
{
    int arr[] = {9,4,8,3,1,2,5};
    len=sizeof(arr)/sizeof(int);
    printf("Initial Array [");
    printArray(arr);
    quickSort(arr,0,len-1);
    return 0;
}

Simple example

Quicksort_partition_-_example.png Below is the version implemented on Wikipedia. 

void quickSort(int arr[], int left, int right) {
      int i = left, j = right;
      int tmp;
      int pivot = arr[(left + right) / 2];

       /* partition */
      while (i <= j) {
            while (arr[i] < pivot)
                  i++;
            while (arr[j] > pivot)
                  j--;

            if (i <= j) {
                  tmp = arr[i];
                  arr[i] = arr[j];
                  arr[j] = tmp;
                  i++;
                  j--;
            }
      };

      /* recursion */
      if (left < j)
            quickSort(arr, left, j);

      if (i < right)
            quickSort(arr, i, right);
}

Favorite site

sitemap