notes blog about

arrays

linked lists

This is an implementation in Go of the selection sort from ch2 of Grokking Algorithms (here is a similar piece):

// selection_sort_test.go
package main

import "testing"

func SelectionSort(s []int) []int {
	var sorted []int
	for range s {
		i := findIndexOfSmallest(s)
		sorted = append(sorted, s[i])
		// remove the item just appended
		s = append(s[:i], s[i+1:]...)
	}
	return sorted
}

func findIndexOfSmallest(s []int) int {
	var smallest int
	var smallestIdx int
	for i, v := range s {
		if i == 0 {
			smallest = v
			smallestIdx = i
			continue
		}
		if v < smallest {
			smallest = v
			smallestIdx = i
		}
	}
	return smallestIdx
}

// --- tests ---

func TestSelectionSort(t *testing.T) {
	type testpair struct {
		s      []int
		sorted []int
	}

	tp := []testpair{
		{[]int{}, []int{}},
		{[]int{1}, []int{1}},
		{[]int{0}, []int{0}},
		{[]int{-1}, []int{-1}},
		{[]int{1, 3, 2}, []int{1, 2, 3}},
		{[]int{-1, 1, -1}, []int{-1, -1, 1}},
		{[]int{100, -100}, []int{-100, 100}},
		{[]int{42, 0, -1, 100, 13}, []int{-1, 0, 13, 42, 100}},
	}

	for _, p := range tp {
		sorted := SelectionSort(p.s)
		if !equals(p.sorted, sorted) {
			t.Errorf("selectionSort: wanted %v, got %v",
				p.sorted, sorted)
		}
	}
}

func equals(a, b []int) bool {
	if len(a) != len(b) {
		return false
	}
	for i, v := range a {
		if v != b[i] {
			return false
		}
	}
	return true
}