Idiomatic quicksort in Go

Question

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?

Answer 1

Here's a solution I built following the Python examples in the book Grokking algorithms. It felt a little less mind bending, so I thought I'd share.

package main

import "fmt"

func main() {
    list := []int{33, 10, 15, 45, 65, 16, 5}

    fmt.Println(quicksort(list))
}

func quicksort(list []int) []int {
    if len(list) < 2 {
        return list
    }
    if len(list) == 2 {
        left, right := 0, len(list)-1
        if list[0] > list[1] {
            list[left], list[right] = list[right], list[left]
        }
        return list
    }

    pivot := list[0]
    var less []int
    var greater []int

    for i := range list {
        if list[i] < pivot {
            less = append(less, list[i])
        }
        if list[i] > pivot {
            greater = append(greater, list[i])
        }
    }

    return append(append(quicksort(less), pivot), quicksort(greater)...)
}

You can run it on the Go Playground here.

Answer 2

func QuickSortArr(arr []int) {
    var i int
    var j int
    var hi int
    var hSave bool
    aLen := len(arr)
    helpArr := make([]int, aLen)
    hSave = true
    var tmpHelp []int
    var tmpArr []int

    for m := 1; m < aLen; m += m {
        i = 0
        j = 0 + m
        hi = 0
        if hSave {
            tmpHelp = helpArr
            tmpArr = arr
        } else {
            tmpHelp = arr
            tmpArr = helpArr
        }
        for i < aLen && j < aLen {
            i2 := i + m
            j2 := j + m
            for i < i2 && i < aLen && j < j2 && j < aLen {
                if tmpArr[i] > tmpArr[j] {
                    tmpHelp[hi] = tmpArr[j]
                    hi++
                    j++
                } else {
                    tmpHelp[hi] = tmpArr[i]
                    hi++
                    i++
                }
            }
            for i < i2 && i < aLen {
                tmpHelp[hi] = tmpArr[i]
                hi++
                i++
            }
            for j < j2 && j < aLen {
                tmpHelp[hi] = tmpArr[j]
                hi++
                j++
            }

            i += m
            j += m
        }

        for i < aLen {
            tmpHelp[hi] = tmpArr[i]
            hi++
            i++
        }
        for j < aLen {
            tmpHelp[hi] = tmpArr[j]
            hi++
            j++
        }

        hSave = !hSave
    }

    if !hSave {
        copy(arr, helpArr)
    }
}

Answer 3

For Go 1.18 and above, using generics:

import (
    "golang.org/x/exp/constraints"
)

func QuickSort[T constraints.Ordered](a []T) {
    if len(a) > 1 {
        quickSort(a, 0, len(a)-1)
    }
}

func quickSort[T constraints.Ordered](a []T, lo, hi int) {
    if lo < hi {
        p := partition(a, lo, hi)
        quickSort(a, lo, p-1)
        quickSort(a, p+1, hi)
    }
}

func partition[T constraints.Ordered](a []T, lo, hi int) int {
    l, p := lo, findPivot(a, lo, hi)
    for r := lo; r < hi; r++ {
        if a[r] < a[p] {
            a[l], a[r] = a[r], a[l]
            l++
        }
    }
    a[l], a[p] = a[p], a[l]
    return l
}

// median of three technique
func findPivot[T constraints.Ordered](a []T, lo, hi int) int {
    mi := (lo + hi) / 2
    if a[lo] > a[mi] {
        a[lo], a[mi] = a[mi], a[lo]
    }
    if a[lo] > a[hi] {
        a[lo], a[hi] = a[hi], a[lo]
    }
    if a[mi] > a[hi] {
        a[mi], a[hi] = a[hi], a[mi]
    }
    a[mi], a[hi-1] = a[hi-1], a[mi]
    return hi - 1
}

Usage:

a := []int{1, 8, 4, 9, 6, 3, 5, 2, 7, 0}
fmt.Println(a, "(original)")
QuickSort(a)
fmt.Println(a, "(sorted)")

b := []string{"tuv", "abc", "jkl", "ghi", "mno", "wxyz", "def", "pqrs"}
fmt.Println(b, "(original)")
QuickSort(b)
fmt.Println(b, "(sorted)")

Answer 4

Could use some thoughts on 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
}

Answer 5

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.

Answer 6

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
}

Answer 7

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.

Answer 8

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