選択ソートとは
選択ソートは、シンプルで直感的に書けるソートアルゴリズムです。
実装が簡単なので、小さなデータをソートするのに適しています。
平均時間計算量、最悪時間計算量がともにО(n²)なので効率的ではありません。
配列(ハッシュテーブル)を作成
8個のデータを持つ配列があります。
Pythonだと以下のように宣言と初期化を行うことができます。
numbers = [7, 4, 3, 8, 1, 5, 2, 6]
randomモジュールを使うことでランダムな配列を作成することもできます。
import random
# random.randint(1, 9)で1〜9の数値を生成、for文で8回実行
numbers = [random.randint(1, 9) for _ in range(8)]
配列から最小値を見つけて入れ替える
選択ソートはまず、最小値を確定したデータの右隣に入れ替えます。
未ソートの配列だと確定したデータはまだ無いので、一番左を入れ替えます。
画像の場合、7と最小値1を入れ替えています。
最小値2を確定したデータの右隣4と入れ替えます。
これを繰り返し、全てのデータが確定したらソート完了です。
選択ソートのプログラム (Python)
def select_sort(data: list[int]) -> list[int]:
len_data = len(data) # 配列の長さ
for i in range(len_data): # リストの各位置に対して最小値を見つけ、その位置と交換するため
min_index = i # 初期値
for j in range(i + 1, len_data): # iより後ろの要素の中から最小値を見つけるため
if data[j] < data[min_index]:
min_index = j
data[i], data[min_index] = data[min_index], data[i]