[Go] Insertion Sort on a slice
Marc
109
GoAlgorithmInsertion Sort

Hello Gophers! =)

You iterate over a slice and you "insert" the "current minimum value" to the left.

// InsertionSort sorts the slice `vals` with the
// insertion sort algorithm.
// Time: O(n^2)
// Space: O(1)
func InsertionSort(vals []int) {
	for i := 1; i < len(vals); i++ {
		for j := i; j > 0 && vals[j-1] > vals[j]; j-- {
			vals[j-1], vals[j] = vals[j], vals[j-1]
		}
	}
}

If you want to test in Go Playground with print:

package main

import "fmt"

// Time: O(n^2)
// Space: O(1)
func main() {
	vals := []int{3, 1, 5, 2, 8, 9, 0}
	insertionSortAndPrint(vals)
}

func insertionSortAndPrint(vals []int) {
	fmt.Println(" i  vals ")
	for i := 1; i < len(vals); i++ {
		for j := i; j > 0 && vals[j-1] > vals[j]; j-- {
			vals[j-1], vals[j] = vals[j], vals[j-1]
		}
		fmt.Printf(" %v ", i)
		fmt.Printf("%v \n", vals)
	}
}

The logic is the same for linked lists.

Note (for interview)

If you cannot use the standard library and if you are not asked to implement this specific algorithm, use a better one where the time complexity is O(nlogn).

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)