In Place Quick Sort

quicksort.go

package main

import (
	"fmt"

	"gitlab.com/NebulousLabs/fastrand"
)

func main() {
	slice := generateIntSlice(20)
	fmt.Printf("Unsorted Slice:\n%v\n", slice)
	quickSort(slice)
	fmt.Printf("Sorted Slice:\n%v\n", slice)
}

// generateIntSlice creates a random int slice of the input size using the
// fastrand package Intn
func generateIntSlice(size int) []int {
	// Initialize int slice, size and capacity
	slice := make([]int, size, size)

	// create random slice
	for i := 0; i < size; i++ {
		slice[i] = fastrand.Intn(200)
	}
	return slice
}

// quickSort sorts a slice in place using a pivot element
func quickSort(arr []int) {
	if len(arr) <= 1 {
		return
	}

	// Define the left and the right index
	left := 0
	right := len(arr) - 1

	// Pick a Pivot index
	pivot := fastrand.Intn(len(arr))

	// Move the Pivot to the right index
	arr[pivot], arr[right] = arr[right], arr[pivot]

	// Set the first element as the pivot
	for i := 0; i < len(arr); i++ {
		if arr[i] < arr[right] {
			arr[i], arr[left] = arr[left], arr[i]
			left++
		}
	}

	// Put Pivot value after the last smaller element
	arr[left], arr[right] = arr[right], arr[left]

	// Call quicksort on two halves
	quickSort(arr[:left])
	quickSort(arr[left+1:])

	return
}