挿入ソート

アルゴリズムクイックリファレンス買いました。

購入動機は、
・アルゴリズムは大学生以来(しかも1-2年の時)やってないのでかなり鈍っている
・グラフ系のアルゴリズムとか学生時代にほとんどやってない
・プログラミングコンテストの予選を突破できるようになりたいので正しいアルゴリズムをきちんと学びたい(正しいアルゴリズムを選べるようになる、計算量を意識できるようになる)
です。

つーことで早速挿入ソート
(多少Pythonicに直した…つもり)

def sort(a):
    for i, e in enumerate(a):
        insert(a, i, a[i])


def insert(a, pos, value):
    i = pos - 1
    while i >= 0 and a[i] > value:
        a[i + 1] = a[i]
        i = i - 1
    a[i + 1] = value


if __name__ == '__main__':
    data = [6, 3, 2, 1, 5, 4]
    sort(data)
    print data

オーダー
最良 O(n)
平均 O(n^2)
最悪 O(n^2)

挿入ソート特徴
要素数が少ない、最初からほぼ整列しているデータに対して有効

感想
かなり男らしい実装だが、
ほぼソートされている場合insert関数のwhileが小さくなるため、
結構高速に動作するらしい。

がんばって一冊みっちり勉強したいとこです。(意気込み)