Pythonの選択ソート完全ガイド｜仕組みと実装方法をわかりやすく解説

Pythonの選択ソートは、リストを「整列済み」と「未整列」の2つの部分に分けて処理するアルゴリズムです。各反復処理で最小値（または最大値）を見つけ出し、それを整列済みの部分へ移動していきます。

リストの並べ替えは、さまざまなプログラムでよく使われる基本的な操作です。たとえば、教師が生徒のテスト結果を分析したい場合、点数を昇順・降順に並べ替えることで、最高点や最低点を簡単に把握できます。

そんなときに役立つのが選択ソートです。選択ソートは、リストを昇順または降順に並べ替えるためのアルゴリズムの一つです。この記事では、Pythonで選択ソートを書く方法を、具体例を交えながら詳しく解説します。

Pythonの選択ソートとは？

Pythonの選択ソートは、リスト内の最小要素を繰り返し見つけ、その要素をリストの特定の端へ移動させる手法です。配列全体が整列されるまでこの処理を続けます。また、最大値を探すよう指示することもでき、どちらのアプローチでもリストを並べ替えられます。

選択ソートでは、まずリストの最初の要素が最小値であると仮定します。次に、その値を2番目の要素と比較し、2番目の要素の方が小さければ、そちらを新しい最小値として扱います。

このプロセスをリストの最後の要素に到達するまで繰り返します。最後の要素に到達した時点で、最小値が未整列部分の先頭に配置されます。

選択ソートの手順を具体例で解説

選択ソートの理解には、実際の例を追うのが一番効果的です。ここでは、生徒の成績リストを昇順に並べ替えてみましょう。以下の未整列リストを考えます。

73

62

61

69

まず、リストの最初の値を最小値とします。選択ソートの各反復では最小要素を見つけ、整列済みサブ配列へ移動していきます。

最小要素を基準にするのは一つの方法で、最大要素を基準にしても選択ソートは機能します。ただし、この例では最小要素を使用します。

次に、最小値を2番目の要素と比較します。2番目の要素の方が小さければ、それが新しい最小値になります。

73と62を比較すると、73は62より大きいため、新しい最小値は62になります。続いて、リスト内の残りの数値もすべて確認していきましょう。

• 61は62（現在の最小値）より大きいか？ いいえ。つまり61の方が小さいので、最小値を61に更新します。
• 69は61（現在の最小値）より大きいか？ はい。何もせず、最小値は61のままです。

この時点で、リストの見た目は変わっていません。

73

62

61

69

リストの末尾に到達したら、最小値をリストの先頭へ移動します。

61

73

62

69

最小値だった61がリストの先頭に移動し、その他の値は一つずつ後ろにずれました。このプロセスを、すべての要素が整列するまで繰り返します。

各反復でのリストの状態は以下の通りです。

1. 73, 62, 61, 69
2. 61, 73, 62, 69
3. 61, 62, 73, 69
4. 61, 62, 69, 73

選択ソートがリスト内のすべての要素を確認し終えると、処理は終了します。

なお、整列済みサブ配列と未整列サブ配列は、私たちからは見えません。アルゴリズムが自動的に配列を並べ替え、未整列部分を管理してくれます。

Pythonで選択ソートを実装する方法

理論はもうバッチリですね！次はいよいよ実践です。ここでは、選択ソートのアルゴリズムをPythonで実装してみましょう。Pythonの配列を受け取り、昇順に並べ替えるプログラムを作成します。

ソート関数を定義する

まず、選択ソートを行うPython関数を定義します。

def sortList(array):
	length = len(array)

	for item in range(length):
		minimum = item

		for i in range(item + 1, length):
			if array[i] < array[minimum]:
				minimum = i

		(array[item], array[minimum]) = (array[minimum], array[item])

まずPythonのlen()メソッドでリストの長さを取得し、それを使ってリスト内の全要素をループするfor文を開始します。

各反復では、minimumの値をリストの先頭要素に設定します。これは前述の解説と同じ流れです。最小値を設定した後、別のfor文が開始され、リスト内の各要素を順番に調べていきます。

リストの各要素について、アルゴリズムは現在の最小値がその要素より大きいかどうかをチェックします。大きくなければ何もせず、大きければ最小値を読み込み中の要素に更新します。

リスト内の全要素の走査が完了すると、アルゴリズムは最小値をリストの先頭へ移動させます。その後、外側のfor文が終了するまで処理を続けます。選択ソートはリストの長さと同じ回数だけ実行されるためです。

ソート関数を呼び出す

このままプログラムを実行しても何も起こりません。まだコードにどの値を使うかを指示していないためです。sortList関数の外側、プログラムの末尾に以下のコードを追加しましょう。

numbers = [73, 62, 61, 69]
sortList(numbers)
print("Sorted list:", numbers)

プログラムを実行すると、次の出力が得られます。

[61, 62, 69, 73]

リストが正しく並べ替えられました。お疲れさまでした！

選択ソートは、降順の並べ替えにも使えます。降順でソートしたい場合は、if文の条件を次のように変更してください。

if array[i] > array[minimum]:

不等号を「より小さい」から「より大きい」に変更しました。これにより、最小値としてリスト内の最大値が設定されるため、リストは降順に並びます。厳密に言えば、minimum変数はmaximum（最大値）として機能することになります。

選択ソートはどんなときに使うべき？

選択ソートは、バブルソートと同様、小規模なリストに適しています。大規模なリストに対しては、挿入ソートなどの他のアルゴリズムほど効率的ではないためです。

一方で、ソートアルゴリズムを学び始めたばかりの人にとって、選択ソートは絶好の入り口となります。他のソートは習得が難しいこともありますが、選択ソートをしっかり理解すれば、さまざまな種類のリスト操作への理解が深まります。

選択ソートの計算量は？

選択ソートの時間計算量はO(n²)です。これは、リスト内の要素数が増えるにつれて、アルゴリズムの計算コストが急激に増加することを意味します。

O(n²)は、このアルゴリズムの最悪ケース・平均ケース・最良ケースすべてに共通する計算量です。ソートの計算量についてさらに学びたい方は、ビッグオー記法に関するガイドもあわせてご覧ください。

まとめ

選択ソートは、データを並べ替える重要な手法の一つです。リスト内の全要素を読み込み、各反復で最小の要素をリストの先頭へ移動させていきます。この処理は、リスト内のすべての要素が読み込まれるまで続きます。

選択ソートは、より効率的なアルゴリズムが存在するため、教育目的以外ではあまり使われません。とはいえ、挿入ソートやマージソートなど、他のソートアルゴリズムを学ぶための足がかりとしては最適です。

Pythonについてさらに学びたい方は、「Pythonの学び方」完全ガイドもぜひ参考にしてください。知識をレベルアップさせるための専門家のアドバイスを掲載しています。