Idiomatic Quick Sort in Go

Question

I look at Go and try to find idiomatic implementations of classical algorithms to understand the language.

I chose quicksort because I am particularly interested in arrays and fragments, instead of copying a deal. After I have omitted some concepts, I want to write a parallel imp.

Can someone please show me the idiomatic implementation of quicksort in Go ?

Answer 1

Well, I am done with this. I don’t know, Go enough to say that this is idiomatic, but I used slices, single-line swaps and a range clause. I was very interested in writing, 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 } 

Answer 2

Take a look at the source of the sort package from the standard library, especially sort.Sort .

Answer 3

Just taking the code from one language, such as C, and simplifying its conversion to another language, such as Go, rarely produces an 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(ba). // . . . } 

This comment is the key 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+(rl)/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, much remains to be done. For example, improving the partitioning algorithm and changing the signature of the qsort function to use the Go interface type.

Answer 4

Now I am just studying, and decided to implement qsort as a simple task, using pipes and parallelism, since in qsort you can sort both halves simultaneously after the array is rotated. I ended up with something like:

 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 are many opportunities for improvement, for example, using a pool of routines instead of creating a new routine for each section and sorting with insertion sort, if len (arr) is small enough or uses something other than [] int. But usually it seems like a good place to start.

Answer 5

You can use some thoughts about this.

 func quickSort(arr []int) []int { sort(arr, 0, len(arr) - 1) return arr } func sort(arr []int, low, high int) { if low < high { pi := partition(arr, low, high) sort(arr, low, pi-1) sort(arr, pi+1, high) } } 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 }