Quicksort
Divide and conquer.
Quicksort is a free C Academy lesson on CoddyKit — lesson 2 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the C Academy learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
Divide and Conquer
Quicksort is a divide-and-conquer sort. It picks a pivot, partitions the array so smaller elements go left and larger go right, then recursively sorts each side.
Average time is O(n log n).
The Partition Step
The key idea is partitioning: rearrange the array around a pivot so that everything left of the pivot is smaller and everything right is larger. The pivot then sits in its final sorted position.
Lomuto Partition Scheme
The Lomuto scheme uses the last element as pivot. It keeps an index i for the boundary of smaller elements and swaps as it scans.
#include <stdio.h>
int partition(int a[], int lo, int hi) {
int pivot = a[hi], i = lo - 1;
for (int j = lo; j < hi; j++)
if (a[j] < pivot) {
i++;
int t = a[i]; a[i] = a[j]; a[j] = t;
}
int t = a[i+1]; a[i+1] = a[hi]; a[hi] = t;
return i + 1;
}
int main(void) {
int a[] = {5, 2, 9, 1, 3};
int p = partition(a, 0, 4);
printf("pivot index = %d\n", p);
for (int i = 0; i < 5; i++) printf("%d ", a[i]);
printf("\n");
return 0;
}The Recursive Sort
Quicksort calls partition, then recurses on the two sub-arrays around the pivot. The base case is a sub-array of size 0 or 1.
#include <stdio.h>
int partition(int a[], int lo, int hi) {
int pivot = a[hi], i = lo - 1;
for (int j = lo; j < hi; j++)
if (a[j] < pivot) { i++; int t=a[i];a[i]=a[j];a[j]=t; }
int t = a[i+1]; a[i+1] = a[hi]; a[hi] = t;
return i + 1;
}
void quicksort(int a[], int lo, int hi) {
if (lo < hi) {
int p = partition(a, lo, hi);
quicksort(a, lo, p - 1);
quicksort(a, p + 1, hi);
}
}
int main(void) {
int a[] = {9, 3, 7, 1, 8, 2, 5};
quicksort(a, 0, 6);
for (int i = 0; i < 7; i++) printf("%d ", a[i]);
printf("\n");
return 0;
}Choosing a Good Pivot
A poor pivot (such as always the last element on sorted input) causes O(n squared) behavior. Better choices spread the partitions more evenly.
- Median-of-three
- Random pivot
Median-of-Three
Median-of-three picks the median of the first, middle, and last elements as pivot, avoiding worst-case behavior on already-sorted data.
#include <stdio.h>
int median_of_three(int a[], int lo, int hi) {
int mid = lo + (hi - lo) / 2;
if (a[mid] < a[lo]) { int t=a[mid];a[mid]=a[lo];a[lo]=t; }
if (a[hi] < a[lo]) { int t=a[hi];a[hi]=a[lo];a[lo]=t; }
if (a[hi] < a[mid]) { int t=a[hi];a[hi]=a[mid];a[mid]=t; }
return mid;
}
int main(void) {
int a[] = {7, 1, 5, 3, 9};
int m = median_of_three(a, 0, 4);
printf("median value = %d\n", a[m]);
return 0;
}Worst-Case Analysis
If every partition splits off just one element, recursion depth becomes n and the cost is O(n squared). This happens with a fixed pivot on sorted or reverse-sorted input.
Randomization makes the worst case extremely unlikely.
Random Pivot
Swapping a random element into the pivot position before partitioning defends against adversarial inputs.
#include <stdio.h>
#include <stdlib.h>
int main(void) {
int a[] = {1, 2, 3, 4, 5};
int lo = 0, hi = 4;
srand(42);
int r = lo + rand() % (hi - lo + 1);
int t = a[r]; a[r] = a[hi]; a[hi] = t; /* move random to pivot slot */
printf("chosen pivot = %d\n", a[hi]);
return 0;
}In-Place and Not Stable
Quicksort sorts in place using only O(log n) stack space on average. However, it is not stable: equal elements may be reordered by the swaps in partitioning.
Tail-Call Optimization
Recursing on the smaller half first and looping on the larger half bounds stack depth to O(log n), preventing stack overflow on large arrays.
Sorting Strings
The same structure sorts any comparable type. Here quicksort orders an array of ints, but swapping the comparison handles other types too.
#include <stdio.h>
int partition(int a[], int lo, int hi) {
int pivot = a[hi], i = lo - 1;
for (int j = lo; j < hi; j++)
if (a[j] < pivot) { i++; int t=a[i];a[i]=a[j];a[j]=t; }
int t = a[i+1]; a[i+1] = a[hi]; a[hi] = t; return i + 1;
}
void quicksort(int a[], int lo, int hi) {
if (lo < hi) { int p = partition(a, lo, hi); quicksort(a, lo, p-1); quicksort(a, p+1, hi); }
}
int main(void) {
int a[] = {42, -7, 0, 100, 13, 13};
quicksort(a, 0, 5);
for (int i = 0; i < 6; i++) printf("%d ", a[i]);
printf("\n");
return 0;
}Quick Check
Test your understanding of quicksort.
Recap
You learned quicksort.
- Partition around a pivot, then recurse on each side
- Average O(n log n), worst case O(n squared)
- Median-of-three or random pivots avoid the worst case
- In place but not stable
Frequently asked questions
Is the “Quicksort” lesson free?
Yes — the full text of “Quicksort” is free to read here on the web, and the C Academy course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the C Academy course, upgrade to CoddyKit PRO.
What will I learn in “Quicksort”?
Divide and conquer. You practise C Academy with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start C Academy?
No prior experience is required. C Academy on CoddyKit is structured for beginners through advanced learners; this is — lesson 2 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “Quicksort” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this C Academy lesson?
Yes. Every C Academy lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.