挿入ソートとは？
挿入ソートは、ソートアルゴリズムの中でも直感的で分かりやすいアルゴリズムです。具体的には、手持ちのトランプを並べ替える際に使用されます。英語では"insertion sort"といいます。
挿入ソートの直感的な解説
トランプを例に挙げます。任意のカードを1枚取ります。そして、その時点のすでにソートされた並びで最も適切な位置に挿入するのです。これを左のカードから順にやっていくことでソートします。
コード例（Python）
insertion_sort.py
def insertion_sort(arr):
"""
挿入ソートを用いてリストを昇順に並び替える関数。
:param arr: ソートするリスト
:return: ソート後のリスト
"""
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
return arr
# 使用例
if __name__ == "__main__":
sample_list = [5, 3, 8, 6, 2, 7, 4, 1]
sorted_list = insertion_sort(sample_list)
print("ソート後のリスト:", sorted_list)
このコードを使用すると、数字の列が昇順にソートされます。つまり、
ソート後のリスト: [1, 2, 3, 4, 5, 6, 7, 8]
と出力されます。
比較演算子を次のように使用することにより、降順にもできます。
while j >= 0 and arr[j] < key: # 条件を `>` から `<` に変更
終わりに
今回はPythonを用いて、挿入ソートの解説をしました。いかがでしたでしょうか。ぜひ感想をいただけると幸いです。