← Back to DSA Course | Chapter 9: Sorting Algorithms | Lesson 5 of 9

Quick Sort

Quick sort is like choosing one kid as a marker and sending shorter kids to one side and taller kids to the other, then doing the same in each group.

In this page:

  1. Basic Idea
  2. Step by Step
  3. Small Array
  4. Practice
  5. Summary
Syntax
markup 
def quick_sort(arr, low, high):
    if low < high:
        p = partition(arr, low, high)
        quick_sort(arr, low, p - 1)
        quick_sort(arr, p + 1, high)

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;
}

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;
}

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;
}

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;
}

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;
}
Related Topics

Merge Sort · Heap Sort · Insertion Sort · Counting Sort

{# common_mistakes/chapter_summary/browser_support: on Hindi pages the view already swaps in the hi_ translation fields (or blanks these out if untranslated), so this renders correctly for both languages without a lang_code check here. #}
Common Mistakes
  1. Choosing the first or last element as pivot on already-sorted data, which gives O(n^2) and deep recursion.
  2. Forgetting to swap the pivot into its final position after partitioning.
  3. Recursing on pivot instead of pivot - 1 and pivot + 1, so the pivot is sorted again forever.
🔒

Chapter Quiz — Complete all 9 topics to unlock

0/9 topics done

Complete these topics first:

← Previous Lesson Merge Sort Next Lesson → Heap Sort

Login to run this code

C/C++/Java/PHP execution requires a free account. Your code is saved — you'll land right back in the editor after logging in.