挿入ソート

Pythonでやってる人を見かけたので俺も。

import random

def insertion_sort(lis):
    for i in range(1,len(lis)):
        tmp = lis.pop(i)
        for j in range(i):
            if tmp < lis[j]:
                lis.insert(j, tmp)
                break
            else:
                lis.insert(i, tmp)
                return lis


l = range(1,10) * 2
random.shuffle(l)
print "unsorted:", 
 l2 = insertion_sort(l)
print "sorted: ", l2

実行結果:

^o^ > python insertion_sort.py
unsorted: [1, 9, 6, 3, 8, 6, 5, 2, 7, 4, 2, 9, 8, 5, 7, 3, 4, 1]
sorted:   [1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9]

Python の for文には else をつけることができるんだ。初めて使った。

カテゴリー: algorithm, Python パーマリンク

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください