implementation of quicksort algorithm in Go, using a randomized pivot. Emphasis on algorithmic clarity over optimization.

quickSort.go

// Quicksort Go, Ian Taylor 2017
// A very simple quicksort implementation with a randomized pivot,
// emphasizing algorithmic clarity over optimization

package main

import (
	"fmt"
	"math/rand"
	"time"
)

// sort an unsorted array in ascending order
func quickSort(A []int) {
	quickSortHelper(A, 0, len(A)-1)
}

func quickSortHelper(A []int, low int, high int) {
	if low >= high {
		return
	}
	pivot_index := partition(A, low, high)
	quickSortHelper(A, low, pivot_index-1)
	quickSortHelper(A, pivot_index+1, high)
}

func partition(A []int, low int, high int) int {
	// random pivot
	pivot_index := random(low, high)
	A[low], A[pivot_index] = A[pivot_index], A[low]

	// pick first element to partition around:
	pivot := A[low]
	i := low + 1

	for j := low + 1; j <= high; j += 1 {
		if A[j] < pivot {
			A[i], A[j] = A[j], A[i]
			i += 1
		}
	}
	A[low], A[i-1] = A[i-1], A[low]
	return i - 1
}

// generate random int in range [min, max]
func random(min int, max int) int {
	return rand.Intn(max+1-min) + min
}

func main() {
	rand.Seed(time.Now().UTC().UnixNano())

	c := []int{13, 48, 1, 4, -4, -3, 20, 0, 100, 99, 11, 3, 7}

	fmt.Println("unsorted:\t", c)
	quickSort(c)
	fmt.Println("quickSort:\t", c, "\n")
}