概要

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

実装は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))
}

参考

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