[Go] Quicksort on a slice
Marc
98
QuicksortGoAlgorithm

Hello Gophers! =)

When you think of Quicksort, think of a pivot and recursive.

  1. You choose a pivot (you decide how, you can take the median between the first, mid and last. We will take it randomly)
  2. You iterate over the slice and move all values smaller than the pivot to the left and keep in memory the location of the last value that is smaller
  3. Once you iterated on all the slice, you move the pivot after the last value that was smaller
  4. You now know that all values at the left of the pivot are smaller than the pivot and the values at the right are bigger, so you can recursively quick sort the slice at its left and sort the slice at its right
// Quicksort sorts the slice `vals` with the
// quicksort algorithm.
// Time: O(nlogn)
// Space: O(logn)
func Quicksort(vals []int) {
	if len(vals) < 2 {
		return
	}

	// Pick a pivot (random)
	// and swap it with the value at the last index
	pivot := rand.Int() % len(vals)
	vals[pivot], vals[len(vals)-1] = vals[len(vals)-1], vals[pivot]
	pivot = len(vals) - 1

	// Pile elements smaller than the pivot on the left
	lastSmaller := 0
	for idx, val := range vals {
		if val < vals[pivot] {
			vals[idx], vals[lastSmaller] = vals[lastSmaller], vals[idx]
			lastSmaller++
		}
	}

	// Place the pivot after the last smaller element
	vals[lastSmaller], vals[pivot] = vals[pivot], vals[lastSmaller]

	// Go down the rabbit hole
	Quicksort(vals[:lastSmaller])
	Quicksort(vals[lastSmaller+1:])
}

If you want to test in Go Playground with print:

package main

import (
	"fmt"
	"math/rand"
)

func main() {
	vals := []int{3, 1, 5, 2, 8, 9, 0}
	Quicksort(vals)
	fmt.Println(vals)
}

// Quicksort sorts the slice `vals` with the
// quicksort algorithm.
// Time: O(nlogn)
// Space: O(logn)
func Quicksort(vals []int) {
	if len(vals) < 2 {
		return
	}

	pivot := rand.Int() % len(vals)
	vals[pivot], vals[len(vals)-1] = vals[len(vals)-1], vals[pivot]
	pivot = len(vals) - 1

	lastSmaller := 0
	for idx, val := range vals {
		if val < vals[pivot] {
			vals[idx], vals[lastSmaller] = vals[lastSmaller], vals[idx]
			lastSmaller++
		}
	}

	vals[lastSmaller], vals[pivot] = vals[pivot], vals[lastSmaller]

	Quicksort(vals[:lastSmaller])
	Quicksort(vals[lastSmaller+1:])
}

Note (for interview)

See all sorting and searching algorithms here (WIP):

If you can, use the sort package of Go's Standard library:

package main

import (
	"sort"
)

func main() {
	// Slice of int
	ints := []int{4, 2, 1, 5, 3, 0}
	sort.Ints(ints)

	// Slice of float64
	floats := []float64{5.2, -1.3, 0.7, -3.8, 2.6}
	sort.Float64s(floats)

	// Slice of string
	strings := []string{"Go", "Bravo", "Gopher", "Alpha", "Grin", "Delta"}
	sort.Strings(strings)

	// Slice of struct
	type person struct {
		name string
		age  int
	}
	person1 := person{"max", 28}
	person2 := person{"eliot", 4}
	person3 := person{"gaby", 27}
	persons := []person{person1, person2, person3}
	sort.Slice(persons, func(i, j int) bool {
		return persons[i].age < persons[j].age
	})
}

Go playground with print here.

Make sure you know the time and space complexity of the language's default sorting algorithm for interviews.
Go uses QuickSort.

I hope it can help!

Comments (0)