ソートアルゴリズム学習(pythonバージョン)の挿入ソート(InsertionSort)

挿入ソート(Insertion Sort)のアルゴリズム記述は単純で直感的なソートアルゴリズムである.秩序化されたシーケンスを構築し、並べ替えられていないデータに対して、並べ替えられたシーケンスを後方から前方にスキャンし、対応する位置を見つけて挿入することが原理です.挿入ソートは実装上、通常はin-placeソート(すなわち、O(1)の余分な空間のソートにのみ使用される)を採用するため、後から前へスキャンする過程で、ソートされた要素を徐々に後ろにシフトし、最新の要素に挿入空間を提供する必要がある.
最悪時間複雑度:O(n^2)
最適時間複雑度:O(n)
平均時間複雑度:O(n^2)
アルゴリズムの説明:
一般に,挿入ソートはin−placeを用いて配列上で実現される.具体的なアルゴリズムは以下の通りである.

  1. 最初の要素から、この要素は

に並べ替えられたと考えられる.

  2. 次の要素を取り出し、並べ替えられた要素のシーケンス内で後方から

をスキャンする.

  3. 要素(並べ替えられた)が新しい要素より大きい場合は、要素を次の位置

に移動します.

  4. 並べ替えられた要素が新しい要素より小さいまたは等しい場所が見つかるまで、手順3を繰り返します.

  5. 新しい要素をこの位置に挿入すると

になります.

  6. 手順2~5

を繰り返す
比較操作のコストが交換操作よりも大きい場合は,二分ルックアップ法を用いて比較操作の数を減らすことができる.このアルゴリズムは,二分ルックアップソートと呼ばれる挿入ソートの変種と考えられる.
コード:

#!/usr/bin/env python

#-*-encoding:utf-8-*-



#InsertionSort

def insertion_sort(param):
    p_len = len(param)
    for i in range(1,p_len):
        key = param[i]
        for j in range(1,i+1)[::-1]:
            if j>0 and key < param[j-1]:
                param[j] = param[j-1]
                param[j-1] = key
    return param

def main():
    param = [5,7,2,9,1]
    print insertion_sort(param)

if __name__=="__main__":
    main()

参考資料:
http://zh.wikipedia.org/wiki/%E6%8F%92%E5%85%A5%E6%8E%92%E5%BA%8F
アルゴリズム導論第二章