挿入ソートを実装してみます。
概要
挿入ソート（インサーションソート）は、ソートのアルゴリズムの一つ。整列してある配列に追加要素を適切な場所に挿入すること。平均計算時間・最悪計算時間がともにO(n2)と遅いが、アルゴリズムが単純で実装が容易なため、しばしば用いられる。安定な内部ソート。基本挿入法ともいう。in-placeアルゴリズムであり、オンラインアルゴリズムである。
挿入ソートを高速化したソート法として、シェルソートが知られている。
挿入ソート – Wikipedia
サンプルコード
import random
data_len = 10
data = random.sample(range(1, 42), data_len)
print(data)
def insertion_sort(collection: list) -> list:
for loop_index in range(1, len(collection)):
insertion_index = loop_index
while (
insertion_index > 0
and collection[insertion_index - 1] > collection[insertion_index]
):
collection[insertion_index], collection[insertion_index - 1] = (
collection[insertion_index - 1],
collection[insertion_index],
)
print(collection)
insertion_index -= 1
return collection
insertion_sort(data)実行結果（例）
[35, 3, 12, 8, 21, 24, 2, 18, 1, 41]
[3, 35, 12, 8, 21, 24, 2, 18, 1, 41]
[3, 12, 35, 8, 21, 24, 2, 18, 1, 41]
[3, 12, 8, 35, 21, 24, 2, 18, 1, 41]
[3, 8, 12, 35, 21, 24, 2, 18, 1, 41]
[3, 8, 12, 21, 35, 24, 2, 18, 1, 41]
[3, 8, 12, 21, 24, 35, 2, 18, 1, 41]
[3, 8, 12, 21, 24, 2, 35, 18, 1, 41]
[3, 8, 12, 21, 2, 24, 35, 18, 1, 41]
[3, 8, 12, 2, 21, 24, 35, 18, 1, 41]
[3, 8, 2, 12, 21, 24, 35, 18, 1, 41]
[3, 2, 8, 12, 21, 24, 35, 18, 1, 41]
[2, 3, 8, 12, 21, 24, 35, 18, 1, 41]
[2, 3, 8, 12, 21, 24, 18, 35, 1, 41]
[2, 3, 8, 12, 21, 18, 24, 35, 1, 41]
[2, 3, 8, 12, 18, 21, 24, 35, 1, 41]
[2, 3, 8, 12, 18, 21, 24, 1, 35, 41]
[2, 3, 8, 12, 18, 21, 1, 24, 35, 41]
[2, 3, 8, 12, 18, 1, 21, 24, 35, 41]
[2, 3, 8, 12, 1, 18, 21, 24, 35, 41]
[2, 3, 8, 1, 12, 18, 21, 24, 35, 41]
[2, 3, 1, 8, 12, 18, 21, 24, 35, 41]
[2, 1, 3, 8, 12, 18, 21, 24, 35, 41]
[1, 2, 3, 8, 12, 18, 21, 24, 35, 41]
