はじめに
こんにちは、鈴木です。データ構造とアルゴリズムの学習のアウトプットも兼ねて、誰かの役に立てばと思い、この記事を投稿するに至りました。ちなみに、言語はPythonを使います。ロジックのみに触れるため、計算量には触れません。（今後、計算量に関する記事は投稿していくつもりです）
今回は選択ソート(Selection Sort/Select Sort)について紹介したいと思います。
選択ソート(Selection Sort/Select Sort)とは
選択ソートとは端的に言えば、先頭の要素から変数に格納して、他の要素と大小比較する並べ替えの手法です。
これだけだと理解に苦しむと思うので、コードで見ていきましょう。
コードで見る
def selection_sort(numbers: list[int]) -> list[int]:
# 入力されたリストの長さを取得
len_numbers = len(numbers)
# 1. 変数を格納するインデックス番号を定めるループ
for i in range(len_numbers):
# 2. i番目(インデックス番号)をmin_idx(変数)に格納
min_idx = i
# 3-1. min_idxと比較するインデックス番号を定めるループ
for j in range(i+1, len_numbers):
# 4-1. numbers[min_idx] が numbers[j]よりも大きい場合
if numbers[min_idx] > numbers[j]:
# 4-2. 変数に格納するインデックス番号を変更
min_idx = j
# 3-2. 変数より、リストの値を更新する
numbers[i], numbers[min_idx] = numbers[min_idx], numbers[i]
return numbers
それでは、具体例を見ていきましょう。
具体例
これは何の変哲もない長さが3のリストです。この要素が1, 2, 3と左から右へと昇順になっているように変更します。
nums = [3, 2, 1]
リストの先頭、3 のインデックス番号( 0 )を min_idx に格納します。
# i = 0
# min_idx = 0
# numbers[min_idx] = 3
nums = [3, 2, 1]
# ↑
# i
# *M
# *min_idx
3と2 を比較します。
# i = 0
# min_idx = 0
# numbers[min_idx] = 3
# j = 1
# numbers[j] = 2
nums = [3, 2, 1]
# ↑ ↑
# i j
# *M
# *min_idx
3 > 2 であることから変数 min_idxの値を更新します。
# i = 0
# min_idx = 1
# numbers[min_idx] = 2
# j = 1
# numbers[j] = 2
nums = [3, 2, 1]
# ↑ ↑
# i *M
# j
# *min_idx
2と1を比較します。
# i = 0
# min_idx = 1
# numbers[min_idx] = 2
# j = 2
# numbers[j] = 1
nums = [3, 2, 1]
# ↑ ↑ ↑
# i *M j
# *min_idx
2 > 1 であることから変数 min_idx の値を更新します。
# i = 0
# min_idx = 2
# numbers[min_idx] = 1
# j = 2
# numbers[j] = 1
nums = [3, 2, 1]
# ↑ ↑
# i *M
# j
# *min_idx
ここでi= 0のときの変数min_idxと他の要素との比較が完了しました。
そして、比較した中で最小の値のインデックス番号をmin_idxに格納することができました。
それでは、nums[i], nums[min_idx] の値を交換します。
# i = 0
# min_idx = 2
# numbers[min_idx] = 1
# j = 2
# numbers[j] = 1
nums = [1, 2, 3]
このように、iのループが一つ終わると比較した中で最小の値を持つ要素をリストの先頭に移動させることができました。選択ソートをこれを繰り返して並び替えを行っていきます。
これで、ソートが完了したように見えますが、まだ残っている処理が実行されます。
2 のインデックス番号( 1 )を min_idx に格納します。
# i = 1
# min_idx = 1
# numbers[min_idx] = 2
nums = [1, 2, 3]
# ↑
# i
# *M
# *min_idx
2と3 を比較します。
# i = 1
# min_idx = 1
# numbers[min_idx] = 2
# j = 2
# numbers[j] = 3
nums = [3, 2, 1]
# ↑ ↑
# i j
# *M
# *min_idx
これは、if文の条件にあてはまらないので、何も処理が起きません。
そして、次にi = 2となりますが、このとき3-1において、range(3, 3) となるため、何も処理が起きません。
これでソートが完了します。
参考
現役シリコンバレーエンジニアが教えるアルゴリズム・データ構造・コーディングテスト入門
動画を用いた視覚的な説明をしているため、とてもわかりやすいです。アルゴリズムを体系的に詳しく理解したい方はご購入をおすすめします。セール時だと、元の値段よりかなり安く購入できます。