クイックソート

分布数え上げソートをやったついでに、クイックソート(quick sort)もやってみた。

import random

def quick_sort(lis):
    if len(lis) == 0:
        return []
    p = lis.pop(0)
    left = [x for x in lis if cmp(x, p) < 0]
    right = [x for x in lis if cmp(x, p) >= 0]
    return quick_sort(left) + [p] + quick_sort(right)


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

l2 = quick_sort(l)
print "sorted: ", l2

実行例:

^o^ > python quick_sort.py
unsorted: [2, 7, 9, 1, 8, 6, 3, 5, 1, 5, 2, 4, 8, 7, 3, 9, 4, 6]
sorted:   [1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9]
カテゴリー: algorithm, Python パーマリンク

コメントを残す

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

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