> udemyで学習する

選択ソートとは?【アルゴリズム紹介・Pythonによる実行】

本記事はPythonの選択ソートについて、学生エンジニアが初心者の方へ向けて優しく解説しています。ソートとは数値や文字列を昇順や降順に並べ替えることで、プログラミングを学ぶ上で非常に重要な道具です。ソートの中でも極めて重要な選択ソートを一緒に学習しましょう。

選択ソートとは?

選択ソートは、データの中から最小値(もしくは最大値)を探索して、未選択の先頭要素へ値を交換していく整列アルゴリズムです。
下の動画がわかりやすく解説していますので御覧ください。
動画の中で「線形探索」言葉が出てきますが、難しく考えずに無視していただいて結構です。


次に、下の動画ではなんとなく、選択ソードの処理速度をイメージできます。


いかがでしたでしょうか。

1. 未選択のデータから最小値を探索
2. 最小値を先頭の要素と交換し整列済みのデータと決定する
3. 決定した以降のデータから一番小さい値を探し、未決定の先頭要素と交換
4. 1〜3を繰り返す

選択ソートは非常に有名で、理解がしやすいソートです。

選択ソートの計算量

平均計算時間最悪計算時間最良計算時間
O(n2O(n2O(n2

選択ソートの計算量は「O(n2)」であり、比較回数は「 n(n-1)/2 」です。
安定ソートではありません。

選択ソートの長所・短所

選択ソートの長所は、アルゴリズム自体がわかりやすく単純であり、コードもシンプルなため実装が簡単な点です。
選択ソートの短所は、安定ソートではない部分であり、より高速にできる改良の余地がある点です。
バブルソートよりも若干高速な整列アルゴリズムです。

Pythonコード

def selection_sort(nums):
    for i in range(len(nums)):
        min = i
        for j in range(i+1, len(nums)):
            if nums[min] > nums[j]:
                min = j
        nums[i], nums[min] = nums[min], nums[i]
    return nums

上記がPythonを用いて作成した選択ソートの関数です。
選択ソートは非常に短い分で簡潔に記述できることが分かると思います。

3行目で、最小値のインデックス番号を格納する変数「min」を宣言しています。
この「min」を利用して最小値と先頭要素を交換します。

選択ソートの実行

上記で作成した関数を使用して、実際に選択ソートをPython環境で実行してみました。
下記がそのコードと実行結果です。

def selection_sort(nums):
    for i in range(len(nums)):
        min = i
        for j in range(i+1, len(nums)):
            if nums[min] > nums[j]:
                min = j
        nums[i], nums[min] = nums[min], nums[i]
    return nums


if __name__ == '__main__':
    nums = [5, 7, 9, 2, 10, 8]
    print(selection_sort(nums))
【実行結果】
[2, 5, 7, 8, 9, 10]

実行結果から、
12行目で宣言した[5, 7, 9, 2, 10, 8]のリストを昇順に上手くソートできていることがわかります。

ということで、本記事は選択ソートについて、Pythonのコードを使用しながらまとめました。
最後まで読んでいただき、ありがとうございました\(^o^)/

超オススメのPC用品

PCを操作する上で、トラックボールマウスが非常におすすめです!
僕も感動したこのマウスを、騙されたと思って使ってみてください!(^^)

外部モニターで2倍以上の効率化が見込めます!
安いものだと、たったの1万円前後なのでおすすめですよー!\(^o^)/