Quick Sort
In this page:
Basic Idea
Quicksort picks a pivot element, partitions the array so smaller values end up before it and larger values after it, and then recursively sorts each side — another divide-and-conquer algorithm, but one that does its main work during the split instead of the merge.
Example: Basic Idea
#include <iostream>
using namespace std;
int partition(int arr[], int low, int high) {
int pivot = arr[high], i = low - 1;
for (int j = low; j < high; j++)
if (arr[j] < pivot) 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) return;
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
int main() {
int arr[] = {7, 2, 1, 6, 8, 5};
quickSort(arr, 0, 5);
for (int x : arr) cout << x << " ";
return 0;
}public class Main {
static int partition(int[] arr, int low, int high) {
int pivot = arr[high], i = low - 1;
for (int j = low; j < high; j++)
if (arr[j] < pivot) { i++; int t = arr[i]; arr[i] = arr[j]; arr[j] = t; }
int t = arr[i + 1]; arr[i + 1] = arr[high]; arr[high] = t;
return i + 1;
}
static void quickSort(int[] arr, int low, int high) {
if (low >= high) return;
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
public static void main(String[] args) {
int[] arr = {7, 2, 1, 6, 8, 5};
quickSort(arr, 0, 5);
System.out.println(java.util.Arrays.toString(arr));
}
}def partition(arr, low, high):
pivot = arr[high]
i = low - 1
for j in range(low, high):
if arr[j] < pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i + 1], arr[high] = arr[high], arr[i + 1]
return i + 1
def quick_sort(arr, low, high):
if low >= high:
return
pi = partition(arr, low, high)
quick_sort(arr, low, pi - 1)
quick_sort(arr, pi + 1, high)
arr = [7, 2, 1, 6, 8, 5]
quick_sort(arr, 0, 5)
print(arr)#include <stdio.h>
int partition(int arr[], int low, int high) {
int pivot = arr[high], i = low - 1;
for (int j = low; j < high; j++)
if (arr[j] < pivot) { i++; int t = arr[i]; arr[i] = arr[j]; arr[j] = t; }
int t = arr[i + 1]; arr[i + 1] = arr[high]; arr[high] = t;
return i + 1;
}
void quickSort(int arr[], int low, int high) {
if (low >= high) return;
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
int main() {
int arr[] = {7, 2, 1, 6, 8, 5};
quickSort(arr, 0, 5);
for (int i = 0; i < 6; i++) printf("%d ", arr[i]);
return 0;
}Login to try C/C++/Java code in the editor
Step by Step
Partitioning walks through the array comparing each element to the chosen pivot, swapping elements so that everything less than the pivot ends up on its left and everything greater ends up on its right, finishing with the pivot in its final sorted position.
Example: Step by Step
#include <iostream>
using namespace std;
int main() {
cout << "Partition walks left to right, swapping smaller-than-pivot values before the boundary, pivot placed last";
return 0;
}public class Main {
public static void main(String[] args) {
System.out.println("Partition walks left to right, swapping smaller-than-pivot values before the boundary, pivot placed last");
}
}print("Partition walks left to right, swapping smaller-than-pivot values before the boundary, pivot placed last")#include <stdio.h>
int main() {
printf("Partition walks left to right, swapping smaller-than-pivot values before the boundary, pivot placed last");
return 0;
}Login to try C/C++/Java code in the editor
Small Array
Tracing a partition step on an array like [7, 2, 1, 6, 8, 5] with the last element as pivot shows how the boundary between 'smaller than pivot' and 'not yet checked' shifts one element at a time as the scan proceeds.
Example: Small Array
#include <iostream>
using namespace std;
int main() {
int arr[] = {7, 2, 1, 6, 8, 5};
int pivot = arr[5], i = -1;
for (int j = 0; j < 5; j++)
if (arr[j] < pivot) cout << "swap " << arr[++i] << " and " << arr[j] << endl;
return 0;
}public class Main {
public static void main(String[] args) {
int[] arr = {7, 2, 1, 6, 8, 5};
int pivot = arr[5], i = -1;
for (int j = 0; j < 5; j++)
if (arr[j] < pivot) System.out.println("swap " + arr[++i] + " and " + arr[j]);
}
}arr = [7, 2, 1, 6, 8, 5]
pivot = arr[5]
i = -1
for j in range(5):
if arr[j] < pivot:
i += 1
print("swap", arr[i], "and", arr[j])#include <stdio.h>
int main() {
int arr[] = {7, 2, 1, 6, 8, 5};
int pivot = arr[5], i = -1;
for (int j = 0; j < 5; j++)
if (arr[j] < pivot) { i++; printf("swap %d and %d\n", arr[i], arr[j]); }
return 0;
}Login to try C/C++/Java code in the editor
Practice
Quicksort's performance depends heavily on pivot choice: a pivot near the median splits the work evenly and gives fast performance, while a consistently poor pivot (like always picking the smallest or largest element) causes uneven splits and much slower behavior — try tracing both cases on a small array.
Example: Practice
#include <iostream>
using namespace std;
int main() {
cout << "A pivot near the median splits work evenly; a pivot near the min or max degrades toward O(n^2)";
return 0;
}public class Main {
public static void main(String[] args) {
System.out.println("A pivot near the median splits work evenly; a pivot near the min or max degrades toward O(n^2)");
}
}print("A pivot near the median splits work evenly; a pivot near the min or max degrades toward O(n^2)")#include <stdio.h>
int main() {
printf("A pivot near the median splits work evenly; a pivot near the min or max degrades toward O(n^2)");
return 0;
}Login to try C/C++/Java code in the editor
Summary
Quicksort averages O(n log n) time, matching merge sort, but its worst case degrades to O(n²) when the pivot choice repeatedly produces unbalanced partitions — in practice it's still often faster than merge sort because it sorts in place without needing extra arrays.
Example: Summary
#include <iostream>
using namespace std;
int main() {
cout << "Quicksort: O(n log n) average, O(n^2) worst case with poor pivot choice";
return 0;
}public class Main {
public static void main(String[] args) {
System.out.println("Quicksort: O(n log n) average, O(n^2) worst case with poor pivot choice");
}
}print("Quicksort: O(n log n) average, O(n^2) worst case with poor pivot choice")#include <stdio.h>
int main() {
printf("Quicksort: O(n log n) average, O(n^2) worst case with poor pivot choice");
return 0;
}Login to try C/C++/Java code in the editor
Chapter Quiz — Complete all 9 topics to unlock
0/9 topics done
Complete these topics first: