[Go] Selection Sort on a slice
Marc
239
GoAlgorithmSelection Sort

Hello Gophers! =)

You iterate over a slice and you "select" the "current minimum value" and switch it with the current position i.

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

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}
	selectionSortAndPrint(vals)
}

func selectionSortAndPrint(vals []int) {
	fmt.Println(" i  vals ")
	for i := 0; i < len(vals)-1; i++ {
		currentMin := i
		for j := i + 1; j < len(vals); j++ {
			if vals[j] < vals[currentMin] {
				currentMin = j
			}
		}
		if currentMin != i {
			vals[currentMin], vals[i] = vals[i], vals[currentMin]
		}
		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)