C Program for Quick Sort with Example and Explanation

A quick sort in C uses a partition function to divide the array and recursively sorts subarrays; the main code includes void quickSort(int arr[], int low, int high) and a partition helper.

Examples

Inputarr = {3, 1, 4, 1, 5}, size = 5

OutputSorted array: 1 1 3 4 5

Inputarr = {10, 7, 8, 9, 1, 5}, size = 6

OutputSorted array: 1 5 7 8 9 10

Inputarr = {1}, size = 1

OutputSorted array: 1

How to Think About It

To sort an array using quick sort, pick a pivot element and rearrange the array so that elements less than the pivot come before it and elements greater come after. Then, apply the same process recursively to the parts before and after the pivot until the whole array is sorted.

Algorithm

1

Choose the last element as pivot.

2

Partition the array so elements less than pivot are left, greater are right.

3

Recursively apply quick sort to left subarray.

4

Recursively apply quick sort to right subarray.

5

Stop when subarray size is 1 or 0.

Code

c

#include <stdio.h>

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

int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = low - 1;
    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return i + 1;
}

void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

int main() {
    int arr[] = {10, 7, 8, 9, 1, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    quickSort(arr, 0, n - 1);
    printf("Sorted array: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

Output

Sorted array: 1 5 7 8 9 10 

Dry Run

Let's trace the array {10, 7, 8, 9, 1, 5} through quick sort.

1

Initial call

quickSort(arr, 0, 5) with arr = {10, 7, 8, 9, 1, 5}

2

Partitioning

Pivot = 5; rearranged array after partition: {1, 5, 8, 9, 10, 7}; pivot index = 1

3

Left subarray sort

quickSort(arr, 0, 0) - single element, no change

4

Right subarray sort

quickSort(arr, 2, 5) with arr = {8, 9, 10, 7}

5

Partitioning right subarray

Pivot = 7; rearranged: {1, 5, 7, 9, 10, 8}; pivot index = 2

6

Sort subarrays around pivot 7

quickSort(arr, 2, 1) no action; quickSort(arr, 3, 5) sorts {9, 10, 8}

7

Partitioning last subarray

Pivot = 8; rearranged: {1, 5, 7, 8, 10, 9}; pivot index = 3

8

Final recursive calls

quickSort(arr, 3, 2) no action; quickSort(arr, 4, 5) sorts {10, 9}

9

Partition last two elements

Pivot = 9; rearranged: {1, 5, 7, 8, 9, 10}; pivot index = 4

10

End recursion

quickSort(arr, 4, 3) no action; quickSort(arr, 5, 5) no action

Step	Array State	Pivot	Pivot Index
1	{10,7,8,9,1,5}	5	1
2	{1,5,8,9,10,7}	7	2
3	{1,5,7,9,10,8}	8	3
4	{1,5,7,8,10,9}	9	4
5	{1,5,7,8,9,10}	-	-

Why This Works

Step 1: Choosing a pivot

The pivot divides the array into parts; elements less than pivot go left, greater go right.

Step 2: Partitioning rearranges elements

Partition moves elements around the pivot so the pivot ends in its correct sorted position.

Step 3: Recursive sorting

Quick sort repeats the process on left and right parts until the whole array is sorted.

Alternative Approaches

Lomuto partition scheme

c

#include <stdio.h>

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

int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = low;
    for (int j = low; j < high; j++) {
        if (arr[j] <= pivot) {
            swap(&arr[i], &arr[j]);
            i++;
        }
    }
    swap(&arr[i], &arr[high]);
    return i;
}

void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

int main() {
    int arr[] = {3, 6, 8, 10, 1, 2, 1};
    int n = sizeof(arr) / sizeof(arr[0]);
    quickSort(arr, 0, n - 1);
    printf("Sorted array: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

This version includes elements equal to pivot on the left side, which can be simpler but may affect performance on duplicates.

Hoare partition scheme

c

#include <stdio.h>

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

int partition(int arr[], int low, int high) {
    int pivot = arr[low];
    int i = low - 1, j = high + 1;
    while (1) {
        do { i++; } while (arr[i] < pivot);
        do { j--; } while (arr[j] > pivot);
        if (i >= j) return j;
        swap(&arr[i], &arr[j]);
    }
}

void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi);
        quickSort(arr, pi + 1, high);
    }
}

int main() {
    int arr[] = {10, 7, 8, 9, 1, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    quickSort(arr, 0, n - 1);
    printf("Sorted array: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

Hoare partition uses two indices moving inward and can be more efficient but is slightly more complex to implement.

Complexity: O(n log n) average, O(n^2) worst case time, O(log n) due to recursion stack space

Time Complexity

Quick sort divides the array and sorts subarrays recursively; average case is O(n log n) because each partition splits the array roughly in half. Worst case is O(n^2) when pivot choices are poor, like always smallest or largest element.

Space Complexity

Quick sort is in-place, so it uses O(1) extra space for swapping, but recursion adds O(log n) space for the call stack.

Which Approach is Fastest?

Quick sort is generally faster than simple sorts like bubble sort. Hoare partition can be faster than Lomuto but is more complex. For nearly sorted data, other sorts like insertion sort may be better.

Approach	Time	Space	Best For
Quick Sort (Lomuto)	O(n log n) avg, O(n^2) worst	O(log n)	General purpose, easy to implement
Quick Sort (Hoare)	O(n log n) avg, O(n^2) worst	O(log n)	Faster partitioning, complex cases
Merge Sort	O(n log n)	O(n)	Stable sort, guaranteed performance