挿入ソート（Pythonによるアルゴリズムとデータ構造）

本記事は、ソフトバンクパブリッシングから発行されている「定本 Cプログラマのためのアルゴリズムとデータ構造 (SOFTBANK BOOKS)」を参考にPythonでアルゴリズムとデータ構造について学習していきます。

今回は、単純な整列アルゴリズムである挿入ソート（Insertion Sort）について学んでいきます。

挿入ソートとは
Pythonで挿入ソートを実装してみる
動作確認
参考書籍

挿入ソートとは

挿入ソート（Insertion Sort）とは、リストの2番目から最後までを順番にスキャンしていき、その中で要素のひとつ前の値よりも小さい限り、リストの先頭に向けて交換していきます。

このようにリストの一部分を整列済みの状態にして置き、値を適切な位置へと挿入していきます。

挿入ソートでも外側と内側でループさせるため、全体では $O(n^2)$ の計算量となりますが、内側のループではリストの隣の値と大小関係を比較し、適切に整列がされていれば交換は発生しないため、計算量は $O(1)$ で済みます。

このようにリストがある程度整列済みの状態であるならば、全体の計算量は $O(n)$ に収まります。

なお、挿入ソートは安定な整列アルゴリズム（データの位置関係が保存される）となります。

Pythonで挿入ソートを実装してみる

それでは、Pythonで挿入ソートを実装してみます。

# insertion_sort.py
import time
import pickle

def insertion_sort(lst):
    for i in range(1, len(lst)):
        j = i
        while j >= 1 and lst[j-1] > lst[j]:
            tmp = lst[j]
            lst[j] = lst[j-1]
            lst[j-1] = tmp
            j -= 1

with open('sample_data.pkl', 'rb') as f:
    lst = pickle.load(f)

start = time.time()
insertion_sort(lst)
print("elapsed {} sec".format(time.time() - start))

動作確認

それでは上記で作成したスクリプトを実行してみます。

事前に1~20,000までの値からランダムに20,000個生成したリストをpickleデータとして保存しておき、これをロードします。

自環境で実行した結果を以下にまとめます。

**データ20,000個を整列した結果一覧**
アルゴリズム名	比較回数	交換回数	所要時間（秒）
Python 組込みメソッド（sort()）	/	/	0.015
Bubble Sort	199,990,000	100,645,566	72.979
Selection Sort	199,990,000	19,999	17.747
Insertion Sort	100,685,552	100,645,566	41.236