Skip to content

Instantly share code, notes, and snippets.

@imwally
Created April 26, 2016 20:45
Show Gist options
  • Save imwally/70f4e5d966fed5c06b7906cfe5f47035 to your computer and use it in GitHub Desktop.
Save imwally/70f4e5d966fed5c06b7906cfe5f47035 to your computer and use it in GitHub Desktop.
The quick sort algorithm written in Go with comments explaining each step.
package main
import (
"fmt"
)
func partition(a []int, lo, hi int) int {
// Select the highest index or right most element in the array
// as the pivot.
p := a[hi]
// The (j) index starts at the lowest index element and
// increments keeping track of each element seen. The (lo)
// element will become the dividing element between elements
// that are lower and the elements that are higher than the
// pivot.
for j := lo; j < hi; j++ {
// Each element (j) is checked against the pivot
// (hi). When (j) is lower it is swapped with the (lo)
// element. A couple different scenarios can happen in
// this loop. When all elements are lower than the
// pivot they stay in place because (lo) and (j) are
// incremented simultaneously, thus they are swapped
// with themselves. When all elements are higher than
// the pivot (hi) they also stay in place but at the
// very end outside of this loop the (lo) and pivot
// (hi) elements are swapped so that the pivot (hi)
// comes before all other elements. The side effect of
// this is when there are various elements that are
// higher and lower, the higher elements are pulled up
// the array until the loop is exhausted. When the
// loop ends, the pivot must be placed where the
// dividing (lo) element is so it sits between the
// lower and higher elements.
if a[j] < p {
a[j], a[lo] = a[lo], a[j]
lo++
}
}
// Finally, the pivot (hi) must be swapped with the dividing
// element (lo). After this swap all elements lower than the
// pivot will become before it and higher elements after it.
a[lo], a[hi] = a[hi], a[lo]
// The swap above places the pivot (hi) into the (lo)
// position. This location must be remembered for each
// recursive call in the quickSort function.
return lo
}
func quickSort(a []int, lo, hi int) {
// When the (lo) element has reaches the (hi) element the
// whole array has been partitioned.
if lo > hi {
return
}
// Partition the array starting at (lo) to (hi). Return the
// pivot position.
p := partition(a, lo, hi)
// Recursively partition all elements on the left side of the
// array, that is from (lo) up to the element just before the
// pivot (p-1).
quickSort(a, lo, p-1)
// Do the same on all elements on the the right side from the
// element after the pivot to the highest index.
quickSort(a, p+1, hi)
}
func main() {
list := []int{55, 90, 74, 20, 16, 46, 43, 59, 2, 99, 79, 10, 73, 1, 68, 56, 3, 87, 40, 78, 14, 18, 51, 24, 57, 89, 4, 62, 53, 23, 93, 41, 95, 84, 88}
quickSort(list, 0, len(list)-1)
fmt.Println(list)
}
@haolian9
Copy link

if lo > hi, you have forgot the lo == hi condition

@imwally
Copy link
Author

imwally commented Mar 5, 2021

Great catch!

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment