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?

Josuejosy

Answer 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
}

Josuejosy

It looks like K&R's C qsort to me. – Korney

Really? That's sad, I was actively trying to not resemble C idioms. Link? – Josuejosy

The C Programming Language, Second Edition – Korney

Nice one there @slezica – Veronaveronese

Beautifully written. I have read through few blogs but this explains quickSort better than few detailed descriptive blogs. – Brigand

This is the best one I have seen so far. – Airglow

Answer 2

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

Maryn

That's a pretty optimized implementation, not at all what I'm looking for, but thanks – Josuejosy

sort.Sort does seem nicely idiomatic though. For example, the golang.org/pkg/sort/#IntSlice wraps []int to be sortable. – Garter

Answer 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.

Korney

Answer 4

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.

Kao

Answer 5

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
}

Grief

in Go, it is often idiomatic to use slices rather than arr, low, high – Osithe

Answer 6

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)")

Auschwitz

Answer 7

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)
    }
}

Oneness

As it’s currently written, your answer is unclear. Please edit to add additional details that will help others understand how this addresses the question asked. You can find more information on how to write good answers in the help center. – Crymotherapy

Answer 8

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.

Appreciative