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?

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.

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
}

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
 {
			a[l], a[r] = a[r], a[l]
			l++
		}
	}
	a[l], a
 = a
, 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)")

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

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.