【Python】挿入ソート【アルゴリズム】

  • 2021年12月14日
  • 2022年8月1日
  • Python
  • 120View
  • 0件

挿入ソート

Python のアルゴリズムレシピとして挿入ソート紹介です。

Wikipedia 挿入ソート

サンプルコード

サンプルコードです。
インプットのリストをそのまま並び替えています。

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]

おしまい!