アルゴリズムとデータ構造 - 選択ソート

アルゴリズム データ構造 選択ソート

プログラミング

2020-02-01 15:59:35

概要

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

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

選択ソート

  • データを昇順または降順に並べ変えるソートの一つ
  • 1番目の要素と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))
}

参考

About the author

Image

bmf san @bmf_san
A web developer in Japan.