Quick sort puts a slice in order by picking one value as a pivot, gathering everything smaller on its left and everything larger on its right, then doing the same thing again on each side.
Strategy
Divide and conquer
Every pivot you place splits the work into two smaller sorts.
- Divide: pick a pivot and move smaller values to its left, larger ones to its right.
- Conquer: run the same routine on the stretch either side of the pivot.
- Combine: nothing to join, because each pivot already landed where it belongs.
Press Step to compare one value at a time. Smaller values swap left, then the pivot drops into the gap.
Purpose
Put a slice of values in order, smallest to largest.
Input
A []int and the stretch of it to sort, given as a low and a high index.
Output
The same slice, sorted in place.
Constraints
- Sorting happens in place, so the order the values arrived in is gone once it runs.
- A list that is already sorted is the slow case, because the pivot never splits the work evenly.
- Equal values can swap past each other, so the sort is not stable.
How quick sort works
You pick one value, the pivot, then shuffle everything smaller to its left and everything bigger to its right. The pivot is now where it belongs. Do the same to each side until every piece is one value.
Most standard libraries reach for it. It sorts in place and is quick on everyday data, but slows right down on a list that is already sorted.
What quick sort keeps track of
| Name | Type | What it is for |
|---|---|---|
| arr | []int | The values you are sorting. Every step shuffles this one slice. |
| low | int | First index of the stretch this call has to sort. |
| high | int | Last index of that same stretch. |
| pivot | int | The value you compare everything else against. |
| i | int | Trails behind, marking the end of the small values found so far. |
| j | int | Scans ahead, pointing at the value you are looking at right now. |
| p | int | Where the pivot landed, which is where the stretch splits in two. |
Walk through it
1 Start with a slice and the stretch to sort
The first call covers the whole thing, from the first index to the last.
arr := []int{8, 3, 7, 4, 9, 1, 5}
quickSort(arr, 0, len(arr)-1)2 Stop if there is nothing to do
One value or none is already sorted, so this call returns.
if low >= high {
return
}3 Pick the pivot and set the marker
Take the last value as the pivot. Start the marker one slot before the stretch.
pivot := arr[high]
i := low - 14 Walk the stretch, moving smaller values left
Walk the stretch. When a value is smaller than the pivot, nudge the marker forward and swap the value into it.
for j := low; j < high; j++ {
if arr[j] < pivot {
i++
arr[i], arr[j] = arr[j], arr[i]
}
}5 Drop the pivot into place
The slot after the marker is where the pivot belongs. Swap it in from the end. That slot splits the stretch.
arr[i+1], arr[high] = arr[high], arr[i+1]
p := i + 16 Repeat on each side
Run the same steps on the values left of the pivot, then on the values right of it.
quickSort(arr, low, p-1)
quickSort(arr, p+1, high)The whole program
Put it together and the slice comes out sorted in place, smallest to largest.
package main
import "fmt"
// partition puts the pivot in its final place and returns that index.
func partition(arr []int, low, high int) int {
pivot := arr[high]
i := low - 1
for 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
}
func quickSort(arr []int, low, high int) {
if low >= high {
return
}
p := partition(arr, low, high)
quickSort(arr, low, p-1)
quickSort(arr, p+1, high)
}
func main() {
arr := []int{8, 3, 7, 4, 9, 1, 5}
quickSort(arr, 0, len(arr)-1)
fmt.Println(arr)
}$ go run main.go
[1 3 4 5 7 8 9]