Idiomatic quicksort in Go

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?

Solution 1:

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
}

Solution 2:

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

Solution 3:

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.