Quick Sort
Quick Sort Settings
Simpler implementation, pivot at end
Simple but can be O(n²) on reverse sorted data
Quick Sort Settings
Simpler implementation, pivot at end
Simple but can be O(n²) on reverse sorted data
Legend
- • Numbers show element values
- • Bottom labels show array indices
- • Colors indicate current operation
- • Height represents value magnitude
Inspector
Legend
- • Numbers show element values
- • Bottom labels show array indices
- • Colors indicate current operation
- • Height represents value magnitude
Inspector
Reference implementation of Quick Sort. Select a language tab to view and copy the code.
/* Lomuto partition scheme */
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++;
int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp;
}
}
int tmp = arr[i + 1]; arr[i + 1] = arr[high]; arr[high] = tmp;
return i + 1;
}
void quick_sort(int arr[], int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quick_sort(arr, low, pi - 1);
quick_sort(arr, pi + 1, high);
}
}#include <vector>
#include <algorithm>
int partition(std::vector<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)
std::swap(arr[++i], arr[j]);
}
std::swap(arr[i + 1], arr[high]);
return i + 1;
}
void quickSort(std::vector<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);
}
}public static 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);
}
}
private static 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++;
int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp;
}
}
int temp = arr[i + 1]; arr[i + 1] = arr[high]; arr[high] = temp;
return i + 1;
}def quick_sort(arr: list[int], low: int, high: int) -> None:
if low < high:
pi = partition(arr, low, high)
quick_sort(arr, low, pi - 1)
quick_sort(arr, pi + 1, high)
def partition(arr: list[int], low: int, high: int) -> int:
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 + 1function quickSort(arr, low = 0, high = arr.length - 1) {
if (low < high) {
const pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
function partition(arr, low, high) {
const pivot = arr[high];
let i = low - 1;
for (let j = low; j < high; j++) {
if (arr[j] <= pivot) {
i++;
[arr[i], arr[j]] = [arr[j], arr[i]];
}
}
[arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];
return i + 1;
}Python — Code Walkthrough
Type hints on both functions
arr: list[int], low: int, high: int) -> NoneBoth quick_sort and partition take the same parameters: the list plus the current subarray bounds. Python lists are mutable and passed by reference, so in-place sorting works.
Base case: low < high
if low < high:Recursion stops when the subarray has fewer than 2 elements. Python has no explicit base-case return needed — the if block simply does nothing when low >= high.
Pivot is the last element
pivot = arr[high]The Lomuto scheme always uses the last element as the pivot. The partition rearranges elements so that everything ≤ pivot ends up to its left.
Tuple swap — no temp needed
arr[i], arr[j] = arr[j], arr[i]Python's simultaneous assignment swaps two list elements without a temporary variable. Used both inside the for loop and at the final pivot placement.
Return the pivot index
return i + 1The partition function returns i+1, the index where the pivot was placed. quick_sort uses this to split into two non-overlapping recursive calls.