Python

Pythonで学ぶアルゴリズム ソート 挿入ソート

挿入ソートを実装してみます。

概要

挿入ソートインサーションソート)は、ソートアルゴリズムの一つ。整列してある配列に追加要素を適切な場所に挿入すること。平均計算時間・最悪計算時間がともに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]