Pythonで学ぶ選択ソートの基本原理と実装方法をわかりやすく解説

本記事では、選択ソート（Selection Sort）の基本的な仕組みと、Python 3.xでの実装方法について詳しく解説します。

選択ソートとは？

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

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

選択ソートの各イテレーション（反復処理）では、未ソート部分から最小要素を取り出し、ソート済み部分の末尾に挿入していきます。この操作を繰り返すことで、最終的に配列全体が昇順に並び替えられます。

アルゴリズムの流れ

1. 先頭の要素を「現在の最小値」として仮定します。
2. 残りの未ソート部分と順番に比較し、より小さい値が見つかれば最小値の位置を更新します。
3. 一巡したら、実際の最小値を先頭の要素と交換（スワップ）します。
4. この手順を配列の末尾まで繰り返します。

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_ は現在比較対象となっている最小値のインデックスを保持しており、他のすべての値との比較に使用されます。内側のループでより小さい値が見つかるたびに min_ が更新され、一巡した後に位置 i の要素と交換されます。

計算量の分析

選択ソートの性能指標は以下の通りです。

• 時間計算量： O(n²) — データ量が増えるほど処理時間が急激に増加します。
• 補助記憶領域（空間計算量）： O(1) — 追加のメモリをほとんど必要としないため、メモリ効率は良好です。

なお、この実装ではすべての変数がグローバルフレーム内で宣言されています。選択ソートは実装がシンプルで理解しやすい反面、計算量がO(n²)であるため、大規模なデータセットにはクイックソートやマージソートなど、より高速なアルゴリズムが適しています。

まとめ

本記事では、選択ソートの基本的な考え方と、Python 3.xにおける具体的な実装方法を紹介しました。シンプルなアルゴリズムながら、ソートの基礎概念を学ぶうえで非常に有用な題材です。ぜひ自分でもコードを動かして、動作を確認してみてください。