a quicksort implementation with some tests

qsort.go

package main

func quicksort(input []int) {
	if len(input) < 2 {
		return
	}

	// pivot is a pointer to the last item in the input array
	pivot := len(input) - 1

	// j is a pointer to items that are larger than the pivot.
	var j int

	for i := 0; i < pivot; i++ {
		if input[i] < input[pivot] {
			// swap the smaller value at position i with the larger value at position j
			input[i], input[j] = input[j], input[i]

			// now that j points to a value that is smaller than the pivot,
			// move it to next place so that it points to a larger value
			j++
		}
	}

	// once we reach the end, then swap the pivot with j since that is the last
	// larger value putting the pivot in the correct place in the input array
	input[pivot], input[j] = input[j], input[pivot]

	// lastly perform quicksort on each half of input array on either side of pivot
	quicksort(input[:j])
	quicksort(input[j+1:])
	return
}

qsort_test.go

package main

import (
	"testing"
)

func TestQuicksort(t *testing.T) {
	testCases := []struct {
		name     string
		input    []int
		expected []int
	}{
		{name: "1. balanced", input: []int{0, 8, 1, 2, 7, 4}, expected: []int{0, 1, 2, 4, 7, 8}},
		{name: "2. already sorted", input: []int{1, 2, 3, 4, 5, 6, 7}, expected: []int{1, 2, 3, 4, 5, 6, 7}},
		{name: "3. almost sorted, last item greater than", input: []int{2, 3, 1, 4, 5, 6}, expected: []int{1, 2, 3, 4, 5, 6}},
		{name: "4. almost sorted, last item less than", input: []int{2, 3, 4, 1}, expected: []int{1, 2, 3, 4}},
		{name: "5. almost reverse sorted, last item less than", input: []int{9, 8, 7, 6, 5, 1}, expected: []int{1, 5, 6, 7, 8, 9}},
		{name: "6. almost reverse sorted, last item greater than", input: []int{8, 7, 6, 5, 4, 9}, expected: []int{4, 5, 6, 7, 8, 9}},
		{name: "7. reverse sorted", input: []int{9, 8, 7, 6, 5, 4}, expected: []int{4, 5, 6, 7, 8, 9}},
		{name: "8. balanced", input: []int{0, 8, 1, 6, 2, 7, 4}, expected: []int{0, 1, 2, 4, 6, 7, 8}},
		{name: "9. all the same", input: []int{5, 5, 5, 5, 5, 5}, expected: []int{5, 5, 5, 5, 5, 5}},
		{name: "10. mostly the same", input: []int{0, 5, 0, 5, 5, 5}, expected: []int{0, 0, 5, 5, 5, 5}},
	}

	for _, tc := range testCases {
		quicksort(tc.input)

		actual := tc.input
		if len(actual) != len(tc.expected) {
			t.Errorf("failed testcase: %s\nwrong length. expected: %d, actual: %d",
				tc.name, tc.expected, actual,
			)
		}

		for i := 0; i < len(tc.expected); i++ {
			if actual[i] != tc.expected[i] {
				t.Errorf("failed testcase: %s\nwrong item at index %d. expected: %v, actual: %v",
					tc.name, i, tc.expected, actual,
				)
				break
			}
		}
	}
}