Quicksort in C

Partition around a pivot, then sort the two halves.

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

static int partition(int *values, int low, int high) {
    int pivot = values[high];
    int boundary = low;
    for (int i = low; i < high; i++) {
        if (values[i] < pivot) {
            swap(&values[i], &values[boundary]);
            boundary++;
        }
    }
    swap(&values[boundary], &values[high]);
    return boundary;
}

void quicksort(int *values, int low, int high) {
    if (low >= high) {
        return;
    }
    int mid = partition(values, low, high);
    quicksort(values, low, mid - 1);
    quicksort(values, mid + 1, high);
}

How it works

1. Lomuto partitioning keeps one scanning index and one boundary.
2. The pivot lands in its final position each pass.
3. Recursion handles the parts either side of it.

Keywords and builtins used here

• for
• if
• int
• partition
• quicksort
• return
• static
• swap
• void

The run, in numbers

Lines

27

Characters to type

527

Tokens

185

Three-star pace

95 tpm

At the three-star pace of 95 tokens a minute, this run takes about 117 seconds.

Type this snippet

Step 4 of 5 in Sorting & searching, step 4 of 20 in Data structures & algorithms.

← Previous Next →

Quicksort in other languages

• Python