Pythonで選択ソートを実装する方法｜仕組みとサンプルコードをわかりやすく解説

この記事では、選択ソート（Selection Sort）の基本的な仕組みと、Python 3.x（およびそれ以前のバージョン）での実装方法について解説します。

選択ソートとは

選択ソートは、ソートされていない部分から最小の要素を繰り返し見つけ出し、先頭側へ移動させることで配列全体を整列していくアルゴリズムです。処理の過程で、対象の配列は次の2つの部分配列に分けられます。

• すでにソートが完了している部分配列
• まだソートされていない部分配列

選択ソートの各イテレーションでは、未ソートの部分配列から最小要素を取り出し、ソート済みの部分配列の末尾に追加していきます。

アルゴリズムの動作イメージ

まず、このアルゴリズムがどのように動作するのか、図で確認してみましょう。

Pythonでの実装例

続いて、実際のコードを見ていきましょう。

A = ['t', 'u', 't', 'o', 'r', 'i', 'a', 'l']

for i in range(len(A)):
    min_ = i
    for j in range(i + 1, len(A)):
        if A[min_] > A[j]:
            min_ = j
    # 最小値を現在の位置にある要素と交換
    A[i], A[min_] = A[min_], A[i]

# 結果の出力
for i in range(len(A)):
    print(A[i])

実行結果

a
i
l
o
r
t
t
u

実行すると、要素が昇順に並べ替えられて出力されます。変数 min_ は、各ループにおいて他のすべての要素と比較される「現時点での最小値」を保持しており、より小さい要素が見つかるたびに更新されます。

計算量の分析

このアルゴリズムの性能指標は以下のとおりです。

• 時間計算量：O(n²)
• 補助空間（メモリ使用量）：O(1)

外側と内側の2重ループですべての要素を比較するため、時間計算量はO(n²)となります。一方、要素の入れ替えは同じ配列内（in-place）で行われるため、必要な追加メモリは定数O(1)で済みます。

まとめ

この記事では、選択ソートの基本的な考え方と、Python 3.xでの実装方法について学びました。選択ソートはコードがシンプルで理解しやすい反面、計算量がO(n²)と大きいため、大量のデータのソートには不向きです。小規模なデータの処理や、ソートアルゴリズムの学習目的には最適な手法といえるでしょう。