C Program to Implement Quick Sort — With Explanation and Complexity

Quick Sort is one of the fastest and most widely used sorting algorithms. It uses a divide-and-conquer strategy: pick a pivot element, partition the array so everything smaller than the pivot is on its left and everything larger is on its right, then recursively sort each side. The pivot ends up in its final sorted position after each partition step.

The C standard library’s qsort() function is built on Quick Sort — knowing how it works makes you a better C programmer.

Algorithm — How It Works

1. Choose a pivot (we use the last element — Lomuto partition scheme)
2. Rearrange the array so all elements ≤ pivot come before it, all elements > pivot come after
3. The pivot is now in its final position
4. Recursively apply steps 1–3 to the left and right subarrays

Step-by-Step Example

Sort [64, 34, 25, 12, 22]:

Initial:       [64, 34, 25, 12, 22]   pivot = 22

After pass 1:  [12, 22, 64, 34, 25]   22 is in final position (index 1)
                    ^-- pivot placed

Left  [12]  → already 1 element, done
Right [64, 34, 25]  pivot = 25

After pass 2:  [25, 64, 34]           25 placed, right = [64, 34]
After pass 3:  [34, 64]               34 placed

Final:         [12, 22, 25, 34, 64] ✓

C Program — Quick Sort

#include <stdio.h>

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

/* Lomuto partition: pivot = last element */
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);
    }
}

void print_array(int arr[], int n) {
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

int main(void) {
    int n;
    printf("Enter number of elements: ");
    scanf("%d", &n);

    int arr[n];
    printf("Enter %d elements: ", n);
    for (int i = 0; i < n; i++)
        scanf("%d", &arr[i]);

    printf("Before sorting: ");
    print_array(arr, n);

    quicksort(arr, 0, n - 1);

    printf("After sorting:  ");
    print_array(arr, n);

    return 0;
}

Code Explanation

• partition() — scans the array with two indices. j moves forward comparing each element to the pivot; i tracks the boundary between the “smaller” and “larger” regions. When arr[j] ≤ pivot, the element belongs in the left region — swap it across the boundary and advance i. After the loop, swap the pivot from arr[high] to its final position at arr[i+1].
• quicksort() — calls partition() to get the pivot’s final index, then recurses on the two sides. The base case low < high stops recursion when the subarray has 0 or 1 elements.
• swap() — takes pointers so the values are exchanged in-place without copying the array.

Sample Output

Enter number of elements: 6
Enter 6 elements: 64 34 25 12 22 11
Before sorting: 64 34 25 12 22 11
After sorting:  11 12 22 25 34 64

Time and Space Complexity

Worst case tip: The O(n²) worst case happens when the array is already sorted and you always pick the first or last element as pivot. In production code, use the “median-of-three” strategy (pick the median of first, middle, and last elements) to avoid this.

Quick Sort vs Other Sorting Algorithms

Quick Sort is the practical winner for most in-memory sorting: its average case matches Merge Sort, but it avoids the O(n) extra memory and has better cache behaviour due to in-place partitioning.

Real-World Applications

• C standard library qsort() — uses a variant of Quick Sort internally
• Database engines for in-memory result set sorting
• Programming language runtimes (V8, CPython) for array sort
• Any scenario needing fast average-case in-place sorting with no memory constraints

Related Sorting Programs in C

• Merge Sort in C — guaranteed O(n log n), stable, needs O(n) extra space
• Insertion Sort in C — best for small or nearly-sorted arrays
• Heap Sort in C — O(n log n) worst case, O(1) space
• Bubble Sort in C
• Selection Sort in C

As an Amazon Associate we earn from qualifying purchases.

Further Reading

The definitive reference for C — The C Programming Language by Brian Kernighan and Dennis Ritchie. Covers every concept on this site: pointers, arrays, structs, file I/O, and the standard library. Worth having on your desk.