import random
def insertion_sort(lst):
# 配列走査するループ
# 左端は「ソート済み」なので1から開始
# 「ソート済み」といってもコード上ではその概念は登場せず、ループカウンタのある時点の値より前がソート済みということになる
for i in range(1, len(lst)):
# ソート済み要素の右端（つまりソート済み要素の中での最大値）と、未ソート要素の左端の大小関係比較
# ループカウンタiの現在の値は未ソート要素、i-1はソート済み要素の右端を指す
# 未ソート要素のほうが小さい場合は、未ソート要素をソート済み要素の中に挿入しないといけない
if lst[i-1] > lst[i]:
# 挿入箇所を探すためのループ
# ソート済み要素の左端から見ていって、未ソート要素のほうが小さくなる最初の位置に挿入すればいい
for j in range(0, i):
if lst[j] > lst[i]:
# Pythonにはinsertメソッドがあるので便利
# そのような機能がない言語の場合は、挿入箇所以降を全部後ろにずらす処理が必要になる
lst.insert(j, lst[i])
# insertメソッドの機能は移動ではなく新規追加なので、元の要素を消す必要がある
# insertメソッドで要素が一つ増えているため、iではなくi+1が元の要素の位置
del lst[i+1]
break
lst = list(range(10))
random.shuffle(lst)
print("ソート前: " + str(lst))
insertion_sort(lst)
print("ソート後: " + str(lst))
