サンプルコード「クイックソート」をご紹介します。
クイックソートは、リストの中から要素をひとつ「ピボット」として選び、ピボット未満の要素とピボットよりも大きな要素とに残りの要素を分けていく再帰的アルゴリズムです。
Pythonのように内包表記を持った言語だととてもシンプル・エレガントに書けるのが特徴です。
def qsort(li):
"""クイックソートを行う
@param li ソート可能な要素を持ったリスト
@return li をソートした結果のリスト
"""
# base case
# 要素が空もしくは1つのリストはそのまま返す
if len(li) < 2:
return li
# recursive case
# 最初の要素をpivotとして、残りの要素をpivot未満と以上に分ける
pivot = li[0]
li_rest = li[1:]
smaller = [x for x in li_rest if x < pivot]
larger = [x for x in li_rest if x >= pivot]
# 分けたグループを再度 qsort に渡してから小さい順に結合する
return qsort(smaller) + [pivot] + qsort(larger)リストを渡して使います。
qsort([]) # => []
qsort([1, 5, 3, 2]) # => [1, 2, 3, 5]
qsort(["tan", "pon", "am"]) # => ['am', 'pon', 'tan']以上です。