【Python】挿入ソートのコード

はじめに

参考文献にある書籍には、挿入ソートの擬似コードが書かれています。これを Python で書き換えたコードを紹介する記事です。

挿入ソートのコード

挿入ソートの擬似コードを Python で書き換えると次のようになります。
なお、降順にソートができるように insertion_sort() 関数の第二引数に reverse があります。 reverse が True の場合は降順にソートし、 False の場合は昇順にソートします。デフォルトは False であるので昇順にソートがデフォルトです。

挿入ソートのコード

def insertion_sort(a, reverse=False):
    array = a.copy()
    if reverse:
        for j in range(1, len(array)):
            key = array[j]
            # array[j] をソート済の列 array[0:j] に挿入する
            i = j - 1
            while i >= 0 and array[i] < key:
                array[i + 1] = array[i]
                i -= 1
            array[i + 1] = key
    else:
        for j in range(1, len(array)):
            key = array[j]
            # array[j] をソート済の列 array[0:j] に挿入する
            i = j - 1
            while i >= 0 and array[i] > key:
                array[i + 1] = array[i]
                i -= 1
            array[i + 1] = key
    return array

if __name__ == '__main__':
    array = [4, 1, 3, 5, 6, 2]
    result1 = insertion_sort(array)
    result2 = insertion_sort(array, reverse=True)
    print(result1)  # [1, 2, 3, 4, 5, 6]
    print(result2)  # [6, 5, 4, 3, 2, 1]

参考文献

• コルメン, T., ライザーソン, C., リベスト, R., シュタイン, C. (著), 浅野 哲夫, 岩野 和生, 梅雄 博司, 山下 将史, 和田 幸一 (訳). 『世界標準MIT教科書 アルゴリズムイントロダクション 第3版 総合版』. 近代科学社 (2013).