Quicksort an array
Sort an integer array in ascending order in place using the quicksort algorithm.
Course progress
Problem 76 of 100
Example → approach → runnable solution
Worked example
See the problem in action
Trace a concrete input through to the verified result.
Example input
numbers = [9, 4, 7, 3, 10, 5]
Expected output
3 4 5 7 9 10
What is happening?
Partition values around a pivot, placing smaller values before it and larger values after it, then repeat on both partitions until sorted.
Solution strategy
Build the right mental model
Partition around the final value as a pivot, place the pivot in its sorted position, then recursively sort both sides.
Core concepts
sorting · divide and conquer
Complexity
Average time O(n log n), worst-case time O(n^2), call-stack space O(log n) on average.
Runnable solution
Learn from working code
Compare languages, copy the code, or open it in the compiler.
Complete C# solution for quicksort
using System;
class Program
{
static void Swap(int[] numbers, int first, int second)
{
int temporary = numbers[first];
numbers[first] = numbers[second];
numbers[second] = temporary;
}
static int Partition(int[] numbers, int low, int high)
{
int pivot = numbers[high];
int boundary = low;
for (int i = low; i < high; i++)
if (numbers[i] <= pivot) Swap(numbers, i, boundary++);
Swap(numbers, boundary, high);
return boundary;
}
static void QuickSort(int[] numbers, int low, int high)
{
if (low >= high) return;
int pivot = Partition(numbers, low, high);
QuickSort(numbers, low, pivot - 1);
QuickSort(numbers, pivot + 1, high);
}
static void Main()
{
int[] values = { 9, 4, 7, 3, 10, 5 };
QuickSort(values, 0, values.Length - 1);
Console.WriteLine(string.Join(" ", values));
}
}Knowledge check
Questions students often ask
What is the main idea behind quicksort an array?
Partition around the final value as a pivot, place the pivot in its sorted position, then recursively sort both sides.
What is the time and space complexity of this solution?
Average time O(n log n), worst-case time O(n^2), call-stack space O(log n) on average.
Do all language tabs solve the same problem?
Yes. Every program uses the same example and produces the verified output shown on this page. The syntax and a few language-specific data structures differ.