Quick Sort in C

Analogy categoryAnalogies

1. Introduction

Quick sort is a highly efficient, in-place, divide-and-conquer sorting algorithm widely used in practice (it underlies many standard library sort functions). Instead of merging sorted halves like merge sort, quick sort works by selecting a 'pivot' element and partitioning the array so that all elements smaller than the pivot come before it and all elements greater come after it. The pivot then sits in its final sorted position, and the same process is recursively applied to the sub-arrays on either side. On average, quick sort runs in O(n log n) time and requires only O(log n) extra space for recursion, making it faster in practice than merge sort despite sharing the same average-case complexity class.

🏏

Cricket analogy: Quick sort is like seeding an IPL knockout bracket around one benchmark team, the pivot, teams weaker go to one side, stronger to the other, and each side is then re-seeded the same way until the whole bracket is sorted.

2. Syntax

void quickSort(int arr[], int low, int high);
int partition(int arr[], int low, int high);

/* Parameters:
   arr  - array of integers to sort in place
   low  - starting index of the current sub-array
   high - ending index of the current sub-array

   Initial call: quickSort(arr, 0, n - 1); */

3. Explanation

This implementation uses the Lomuto partition scheme with the last element as the pivot. partition() picks arr[high] as the pivot, then uses an index i to track the boundary of elements known to be smaller than the pivot. It scans j from low to high - 1; whenever arr[j] < pivot, it increments i and swaps arr[i] with arr[j], growing the 'smaller than pivot' region. After the scan, it swaps arr[i + 1] with arr[high], placing the pivot right after the smaller elements and before the larger ones, and returns i + 1 as the pivot's final sorted index. quickSort() then recursively sorts the sub-array to the left of the pivot (low to pivotIndex - 1) and to the right (pivotIndex + 1 to high).

🏏

Cricket analogy: The Lomuto partition is like a selector using the last player trialed as the benchmark (pivot), keeping an index of confirmed squad members (i) while scanning remaining trialists (j), swapping in anyone better than the benchmark, then slotting the benchmark player right after the confirmed group.

Worked trace on [10, 7, 8, 9, 1, 5] with pivot = arr[high] = 5: i starts at -1. j=0: arr[0]=10, not < 5, skip. j=1: arr[1]=7, not < 5, skip. j=2: arr[2]=8, not < 5, skip. j=3: arr[3]=9, not < 5, skip. j=4: arr[4]=1, 1 < 5, so i becomes 0, swap arr[0] and arr[4] -> [1,7,8,9,10,5]. Loop ends; swap arr[i+1]=arr[1] with arr[high]=arr[5] -> [1,5,8,9,10,7]. Pivot 5 is now at index 1, its correct sorted position, with quickSort then recursing on [1] (left, already sorted) and [8,9,10,7] (right, indices 2-5).

🏏

Cricket analogy: Tracing quick sort on scores [10,7,8,9,1,5] with pivot 5 is like a selector scanning five trialists' fitness scores against a benchmark of 5, finding only the score of 1 beats it, swapping it forward, then placing the benchmark 5 right after it, leaving [1,5,8,9,10,7] with 5 correctly seated at index 1.

4. Example

#include <stdio.h>

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

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 pivotIndex = partition(arr, low, high);
        quickSort(arr, low, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, high);
    }
}

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

int main(void) {
    int arr[] = {10, 7, 8, 9, 1, 5};
    int n = sizeof(arr) / sizeof(arr[0]);

    quickSort(arr, 0, n - 1);
    printArray(arr, n);
    return 0;
}

5. Output

text

1 5 7 8 9 10

6. Key Takeaways

Average-case time complexity is O(n log n), which is what makes quick sort practical for general-purpose use.
Worst-case time complexity is O(n^2), which occurs when the pivot is repeatedly the smallest or largest element (e.g., an already-sorted array with last-element pivoting).
Quick sort is an in-place algorithm requiring only O(log n) extra space for the recursion stack (average case).
It is not a stable sort by default, since the partition step can reorder equal elements.
Randomized or median-of-three pivot selection helps avoid the O(n^2) worst case on already-sorted input.

Practice what you learned

1. What is the average-case time complexity of quick sort?

2. When does quick sort's worst-case O(n^2) behavior typically occur?

3. In the Lomuto partition scheme shown, what does the returned index represent?

4. What is the space complexity of quick sort's recursion in the average case?

5. Is the quick sort implementation shown in the example a stable sort?

Was this page helpful?

Merge Sort in C

Time Complexity in C

Related Study Notes in Programming

Browse all study notes

Programming

Apache Spark Study Notes

Programming · 30 topics

Programming

Apache Flink Study Notes

Programming · 30 topics

Programming

Hadoop Study Notes

Programming · 30 topics

Programming

Snowflake Study Notes

Programming · 30 topics

Programming

Apache Airflow Study Notes

Programming · 30 topics

Programming

dbt (Data Build Tool) Study Notes

Programming · 30 topics

Topics covered

#CProgrammingStudyNotes#Programming#QuickSortInC#Quick#Sort#Syntax#Explanation#Algorithms#StudyNotes#SkillVeris

1. Introduction

2. Syntax

3. Explanation

4. Example

5. Output

6. Key Takeaways

Practice what you learned

You May Also Like

Related Reading

Related Study Notes in Programming

Topics covered