Overview

Learn algorithms and data structures with reference to Algorithm Encyclopedia.

The implementation is also available on github - bmf-san/road-to-algorithm-master.

Selection Sort

• A sorting method that arranges data in ascending or descending order
• Compares the smallest value among the elements from the second onward with the first element, and if the order is reversed, swaps them. This operation is repeated until the second to last element of the data sequence.

Time Complexity

• Best and average time complexity
  • Same as bubble sort, О(n²)

Implementation

package main

func selectionSort(n []int) []int {
	for i := 0; i < len(n); i++ {
		min := i

		// Compare the smallest value in the data with the first value
		for j := i + 1; j < len(n); j++ {
			if n[j] < n[min] {
				min = j
			}
		}

		// Swap
		n[i], n[min] = n[min], n[i]
	}

	return n
}

func main() {
	n := []int{2, 1, 5, 7, 9}
	fmt.Println(selectionSort(n))
}

References

• Algorithms and Data Structures