クイックソートは、適当な値（これを pivot という）を選び、その pivot よりも大きい値を配列の右側に移動し、pivot よりも小さい値を配列の左側に移動して、配列を 2 つに分割する。次に、分割された 2 つの配列それぞれに対して、pivot を選びさらに分割を行う。分割を再帰的に行なって行ったとき、最終的には整列済みの部分配列が得られる。最後にこれらの部分配列を結合すれば、整列済みの配列が得られる。クイックソートは、データの比較回数と交換回数が、他のソートアルゴリズムに比べて少ないので、値がランダムな配列を整列する場合に、効率が最も良いと言われている。

C/C++ でクイックソートを実装する上で、具体的に次のような手順を踏む。

1. n 個の要素を持つ入力配列 A[1..n] の最後要素を pivot とする。すなわち pivot = A[n] とする。
2. j = 1, 2, ..., i, ..., n-1 それぞれに対して、A[j] と pivot (=A[n]) を比較し、A[j] が大きければ、それを配列の左側の要素を入れ替える。この入れ替えが終わると、pivot は i の位置に移動する。
3. 位置 i の左側を部分配列として、その部分配列の最後の要素を pivot として、手順 2 を行う。
4. 位置 i の右側を部分配列として、その部分配列の最後の要素を pivot として、手順 2 を行う。

#include <stdio.h>

void swap(int* a, int* b)
{
    int t = *a;
    *a = *b;
    *b = t;
}

int partition (int array[], int l, int r) {
    int pivot = array[r];
    int i = (l - 1);

    for (int j = l; j <= r - 1; j++) {
        if (array[j] <= pivot) {
            i++;
            swap(&array[i], &array[j]);
        }
    }
    swap(&array[i + 1], &array[r]);
    return (i + 1);
}

void quickSort(int array[], int l, int r) {
    if (l < r) {
        int pivot = partition(array, l, r);
        quickSort(array, l, pivot - 1);
        quickSort(array, pivot + 1, r);
    }
}



int main (void) {

    int i;
    int array[10] = {3, 6, 1, 7, 2, 0, 4, 5, 9, 8};

    printf("       array: ");
    for (i = 0; i < sizeof(array) / sizeof(array[0]); i++) {
        printf("%d ", array[i]);
    }
    printf("\n");

    quickSort(array, 0, sizeof(array) / sizeof(array[0]) - 1);

    printf("sorted array: ");
    for (i = 0; i < sizeof(array) / sizeof(array[0]); i++) {
        printf("%d ", array[i]);
    }
    printf("\n");

    return 0;
}