【基本情報技術者試験】選択ソートをPythonで実装

前回に引き続きソートアルゴリズムをPythonで実装していきます。今回は選択ソートを扱います。

1. 基本交換法（バブルソート）
2. 基本選択法（選択ソート）←今回の対象
3. 基本挿入法（挿入ソート）
4. シェルソート
5. クイックソート
6. マージソート
7. ヒープソート

選択ソートとは？

選択ソートとは配列から最小値を探し、配列の先頭要素と入れ替えていくことで並べ替えるアルゴリズムのことです。基本選択法とも呼ばれます。

n個の数列があったときに最初はn個の中で最小の値を1番目の値と入替、次にn-1個の中で最小の値を2番目の値と入替・・・にというような形で繰り返していきます。例えば4, 2, 5, 3, 1という数列があったときに下記のように更新していきます。（赤字部分が固定箇所になります。）

① 1, 2, 5, 3, 4 （最小値の1と４を入替）
② 1, 2, 5, 3, 4 （最小値は2なので変更なし）
③ 1, 2, 3, 5, 4 （最小値の1と４を入替）
④ 1, 2, 3, 4, 5 （最小値の1と４を入替）

実際のPythonのコードは下記になります。

listNum = [4, 2, 5, 3, 1]

listNum

[4, 2, 5, 3, 1]

lenNum = len(listNum)
for i in range(lenNum):
  minIdx = i
  for j in range(i + 1, lenNum):
    if listNum[minIdx] > listNum[j]:
      minIdx = j
  listNum[i], listNum[minIdx] = listNum[minIdx], listNum[i]

listNum

[1, 2, 3, 4, 5]

上記のコードでも問題なく動きますが、Pythonではmin関数と配列のインデックスを求める関数があるので、それを利用すると下記のように簡潔に記載することができます。

lenNum = len(listNum)
for i in range(lenNum):
  minIdx = listNum.index(min(listNum[i:]))
  listNum[i], listNum[minIdx] = listNum[minIdx], listNum[i]

listNum

[1, 2, 3, 4, 5]

選択ソートでのソート方法は以上となります。
次回は挿入ソートをPythonで実装します。