insertion sort with tests and benchmarks

bench_test.go

package main

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

const (
	random        = 0
	sorted        = 1
	reverseSorted = 2
	allsame       = 3
	halfsame      = 4
	almostallsame = 5
	balanced      = 6
)

var benchCases = []struct {
	name      string
	size      int
	inputType int
}{
	{"10___ random", 10, random},
	{"100__ random", 100, random},
	{"1000_ random", 10000, random},
	{"10000 random", 100000, random},
	{"10___ sorted", 10, sorted},
	{"100__ sorted", 100, sorted},
	{"1000_ sorted", 1000, sorted},
	{"10000 sorted", 10000, sorted},
	{"10___ reverse", 10, reverseSorted},
	{"100__ reverse", 100, reverseSorted},
	{"1000_ reverse", 1000, reverseSorted},
	{"10000 reverse", 10000, reverseSorted},
	{"10___ allsame", 10, allsame},
	{"100__ allsame", 100, allsame},
	{"1000_ allsame", 1000, allsame},
	{"10000 allsame", 10000, allsame},
	{"10___ halfsame", 10, halfsame},
	{"100__ halfsame", 100, halfsame},
	{"1000_ halfsame", 1000, halfsame},
	{"10000 halfsame", 10000, halfsame},
	{"10___ almostallsame", 10, almostallsame},
	{"100__ almostallsame", 100, almostallsame},
	{"1000_ almostallsame", 1000, almostallsame},
	{"10000 almostallsame", 10000, almostallsame},
	{"10___ balanced", 10, balanced},
	{"100__ balanced", 100, balanced},
	{"1000_ balanced", 1000, balanced},
	{"10000 balanced", 10000, balanced},
}

func BenchmarkQuicksort(b *testing.B) {
	rand.Seed(time.Now().UnixNano())
	for _, bm := range benchCases {

		b.Run(bm.name, func(b *testing.B) {
			for n := 0; n < b.N; n++ {
				input := createTestInput(bm.size, bm.inputType)
				b.ResetTimer()
				quicksort(input)
			}
		})

	}
}
func BenchmarkInsertsort(b *testing.B) {
	rand.Seed(time.Now().UnixNano())
	for _, bm := range benchCases {

		b.Run(bm.name, func(b *testing.B) {
			for n := 0; n < b.N; n++ {
				input := createTestInput(bm.size, bm.inputType)
				b.ResetTimer()
				insertionsort(input)
			}
		})

	}
}

func createTestInput(testcaseSize int, inputType int) []int {
	input := make([]int, testcaseSize)

	for i := range input {
		switch inputType {
		case allsame:
			input[i] = 3
		case sorted:
			input[i] = i
		case reverseSorted:
			input[i] = testcaseSize - i
		case halfsame:
			input[i] = 1
			if i%2 == 0 {
				input[i] = 4
			}
		case almostallsame:
			input[i] = 1
			if i == 0 || i == len(input)-1 {
				input[i] = 4
			}
		case balanced:
			input[i] = testcaseSize - i
			if i%2 == 0 {
				input[i] = i - testcaseSize
			}
		case random:
			input[i] = rand.Intn(int(testcaseSize))
		default:
			input[i] = rand.Intn(int(testcaseSize))
		}
	}
	return input
}

insertion.go

func insertionsort(input []int) []int {
	// sortedToHere points to the index of the input array where its been sorted to so far
	var sortedToHere int

	for elementToSort := sortedToHere + 1; elementToSort < len(input); elementToSort++ {
		// all items to the right of the sorted section of the array must be
		// larger than the last item in the sorted section
		// therefore if we come across a smaller value, then we need to move it
		// into the correct place of the sorted portion
		if input[elementToSort] < input[sortedToHere] {
			input[elementToSort], input[sortedToHere] = input[sortedToHere], input[elementToSort]

			// keep moving the smaller item to the left until its
			// in the correct sorted position
			currentlySorting := sortedToHere
			sortedToHere = elementToSort
			if currentlySorting == 0 {
				continue
			}
			for input[currentlySorting] < input[currentlySorting-1] {
				input[currentlySorting], input[currentlySorting-1] = input[currentlySorting-1], input[currentlySorting]
				currentlySorting--
				if currentlySorting < 1 {
					break
				}
			}
			continue
		}
		sortedToHere++
	}
	return input
}

insertion_test.go

package main

import (
	"testing"
)

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

func TestQuicksort(t *testing.T) {
	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,
			)
		}

		if !isSorted(tc.input) {
			t.Errorf("failed testcase: %s\nshould be sorted, actual: %v",
				tc.name, actual,
			)
		}
	}
}

func TestInsertionSort(t *testing.T) {

	for _, tc := range testCases {
		insertionsort(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,
			)
		}

		if !isSorted(tc.input) {
			t.Errorf("failed testcase: %s\nshould be sorted, actual: %v",
				tc.name, actual,
			)
		}
	}
}

func isSorted(arr []int) bool {
	for i := 0; i < len(arr)-1; i++ {
		if arr[i] > arr[i+1] {
			return false
		}
	}
	return true
}