Python練習(挿入ソート)

Pythonで挿入ソート

挿入ソートとは、ソート済みの要素に、順に要素を適切な位置へ挿入することで、
すべての要素をソートさせる考え方。計算量はO(N^2)。
ただし、バブルソートより高速であることが多い(値の入れ替え処理が少なく済むため)

コード(Python)

#coding: UTF-8

#挿入ソート

x = [4,50,3,10,88,39,2,15]

for i in range(1,len(x)):
    j = i
    while (j > 0) and (x[j-1] > x[j]) :
        tmp = x[j-1]
        x[j-1] = x[j]
        x[j] = tmp
        j -= 1
    print x

print "-"*30
print x

出力

[4, 50, 3, 10, 88, 39, 2, 15]
[3, 4, 50, 10, 88, 39, 2, 15]
[3, 4, 10, 50, 88, 39, 2, 15]
[3, 4, 10, 50, 88, 39, 2, 15]
[3, 4, 10, 39, 50, 88, 2, 15]
[2, 3, 4, 10, 39, 50, 88, 15]
[2, 3, 4, 10, 15, 39, 50, 88]
------------------------------
[2, 3, 4, 10, 15, 39, 50, 88]

参考文献

アルゴリズムを学ぼう