I'm taking a look at Go, and was trying to find idiomatic implementations of classic algorithms to get a feel for the language.
I chose quicksort because I'm particularly interested in the arrays vs slices, in-place vs copy deal. After I settle some concepts down, I want to write a parallel impl.
Can someone please show me an idiomatic implementation of quicksort in Go?
Well, I ended up with this. I don't know enough Go to say it's idiomatic, but I used slices, one-line swaps and a range clause. It's been pretty informative for me to write, so I thought I should share.
func qsort(a []int) []int {
if len(a) < 2 { return a }
left, right := 0, len(a) - 1
// Pick a pivot
pivotIndex := rand.Int() % len(a)
// Move the pivot to the right
a[pivotIndex], a[right] = a[right], a[pivotIndex]
// Pile elements smaller than the pivot on the left
for i := range a {
if a[i] < a[right] {
a[i], a[left] = a[left], a[i]
left++
}
}
// Place the pivot after the last smaller element
a[left], a[right] = a[right], a[left]
// Go down the rabbit hole
qsort(a[:left])
qsort(a[left + 1:])
return a
}
Take a look at the source of the sort package from the standard library, particularily sort.Sort.
Simply taking code from one language, for example C, and simplistically converting it to another language, for example Go, rarely produces idiomatic code.
Go sort package -- sort.c source file
func quickSort(data Interface, a, b, maxDepth int) { // . . . // Avoiding recursion on the larger subproblem guarantees // a stack depth of at most lg(b-a). // . . . }
This comment is a clue that implementing a recursive solution may not be the best strategy. Go uses short stacks.
Here's an iterative Quicksort solution.
package main
import (
"fmt"
"math/rand"
"time"
)
type Item int
type Items []Item
// Algorithms and Data Structures, N. Wirth
// http://www.ethoberon.ethz.ch/WirthPubl/AD.pdf
// 2.3.3 Partition Sort, Quicksort, NonRecursiveQuickSort.
func qSort(a Items) {
const M = 12
var i, j, l, r int
var x Item
var low, high = make([]int, 0, M), make([]int, 0, M)
low, high = append(low, 0), append(high, len(a)-1)
for { // (*take top request from stack*)
l, low = low[len(low)-1], low[:len(low)-1]
r, high = high[len(high)-1], high[:len(high)-1]
for { // (*partition a[l] ... a[r]*)
i, j = l, r
x = a[l+(r-l)/2]
for {
for ; a[i] < x; i++ {
}
for ; x < a[j]; j-- {
}
if i <= j {
a[i], a[j] = a[j], a[i]
i++
j--
}
if i > j {
break
}
}
if i < r { // (*stack request to sort right partition*)
low, high = append(low, i), append(high, r)
}
r = j // (*now l and r delimit the left partition*)
if l >= r {
break
}
}
if len(low)+len(high) == 0 {
break
}
}
}
func main() {
nItems := 4096
a := make(Items, nItems)
rand.Seed(time.Now().UnixNano())
for i := range a {
a[i] = Item(rand.Int31())
}
qSort(a)
for i := range a[1:] {
if a[i] > a[i+1] {
fmt.Println("(* sort error *)")
}
}
}
Clearly, there is more to be done. For example, improving the partitioning algorithm and changing the qsort function signature to use a Go interface type.
I'm just learning go right now and decided to implement qsort as a simple task, using channels and parallelism since in qsort you can sort both halves concurrently after pivoting the array. I ended up with smth like that:
package main
import (
"fmt"
"math/rand"
"time"
)
func qsort_pass(arr []int, done chan int) []int{
if len(arr) < 2 {
done <- len(arr)
return arr
}
pivot := arr[0]
i, j := 1, len(arr)-1
for i != j {
for arr[i] < pivot && i!=j{
i++
}
for arr[j] >= pivot && i!=j{
j--
}
if arr[i] > arr[j] {
arr[i], arr[j] = arr[j], arr[i]
}
}
if arr[j] >= pivot {
j--
}
arr[0], arr[j] = arr[j], arr[0]
done <- 1;
go qsort_pass(arr[:j], done)
go qsort_pass(arr[j+1:], done)
return arr
}
func qsort(arr []int) []int {
done := make(chan int)
defer func() {
close(done)
}()
go qsort_pass(arr[:], done)
rslt := len(arr)
for rslt > 0 {
rslt -= <-done;
}
return arr
}
func main() {
fmt.Println("About to sort.")
rand.Seed(time.Now().UTC().UnixNano())
arr_rand := make([]int, 20)
for i := range arr_rand {
arr_rand[i] = rand.Intn(10)
}
fmt.Println(arr_rand)
qsort(arr_rand)
fmt.Println(arr_rand)
}
There's plenty of room for improvement here like using a pool of go-routines instead of spawning a new go-routine for each partition, and sorting with insertion sort if len(arr) is small enough or using something other than []int. But generally it looks like a good place to start.