挿入ソート
Python のアルゴリズムレシピとして挿入ソート紹介です。
サンプルコード
サンプルコードです。
インプットのリストをそのまま並び替えています。
def insertion_sort(xs):
for j in range(1, len(xs)):
key = xs[j]
i = j - 1
while i >= 0 and xs[i] > key:
xs[i + 1] = xs[i]
i -= 1
xs[i + 1] = key
print(xs)
if __name__ == '__main__':
xs = [8, 4, 3, 7, 6, 5, 2, 1]
print('initial:', xs)
insertion_sort(xs)
print('sorted :', xs)以下は出力結果です。
❯ python3 insertion_sort.py
initial: [8, 4, 3, 7, 6, 5, 2, 1]
[4, 8, 3, 7, 6, 5, 2, 1]
[3, 4, 8, 7, 6, 5, 2, 1]
[3, 4, 7, 8, 6, 5, 2, 1]
[3, 4, 6, 7, 8, 5, 2, 1]
[3, 4, 5, 6, 7, 8, 2, 1]
[2, 3, 4, 5, 6, 7, 8, 1]
[1, 2, 3, 4, 5, 6, 7, 8]
sorted : [1, 2, 3, 4, 5, 6, 7, 8]サンプルコード（副作用なし）
もうひとつ、副作用なし版のサンプルコードです。
新規リストを挿入しながら生成しています。
def insertion_sort(xs):
ys = []
for x in xs:
ref = len(ys)
for i in range(0, len(ys)):
if x < ys[i]:
ref = i
break
ys.insert(ref, x)
print(ys)
return ys
if __name__ == '__main__':
xs = [8, 4, 3, 7, 6, 5, 2, 1]
print('initial:', xs)
ys = insertion_sort(xs)
print('sorted :', ys)出力結果です。
❯ python3 insertion_sort_fn.py
initial: [8, 4, 3, 7, 6, 5, 2, 1]
[8]
[4, 8]
[3, 4, 8]
[3, 4, 7, 8]
[3, 4, 6, 7, 8]
[3, 4, 5, 6, 7, 8]
[2, 3, 4, 5, 6, 7, 8]
[1, 2, 3, 4, 5, 6, 7, 8]
sorted : [1, 2, 3, 4, 5, 6, 7, 8]おしまい！