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

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

選択ソートとは？

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

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

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

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

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

選択ソートの計算量

選択ソートの計算量は「Ｏ（ｎ²）」であり、比較回数は「 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を用いて作成した選択ソートの関数です。
選択ソートは非常に短い分で簡潔に記述できることが分かると思います。

３行目で、最小値のインデックス番号を格納する変数「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]

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

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

超オススメのPC用品

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

外部モニターで２倍以上の効率化が見込めます！
安いものだと、たったの１万円前後なのでおすすめですよー！＼(^o^)／