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]
参考文献
アルゴリズムを学ぼう