概要

アルゴリズム図鑑を参考に、アルゴリズムとデータ構造を学ぶ。

実装はgithub - bmf-san/road-to-algorithm-masterにも置いてある。

選択ソート

• データを昇順または降順に並べ変えるソートの一つ
• １番目の要素と2番目以降の要素の中で最小の値を比較して、順序が逆なら入れ変えを行う、という操作をデータ列の最後の一つ手前まで繰り返す

計算時間

• 最良計算時間、平均計算時間
  • バブルソートと同じくО(n²)

実装

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))
}

参考

• アルゴリズムとデータ構造