pythonでクイックソートのアルゴリズム

関数の再帰呼び出しを使って、リストを昇順に並べるクイックソートのコードを作ってみました。

クイックソートとは
１　基準となる数値(pivot)を決める。
２　pivotより小さい集団と大きい集団とに二分する。
３　小さい集団からpivotを選び二分する。大きい集団も同様に二分。
４　さらに二分された集団から、またpivotを選び・・・
５　集団の個数が1個になったら終了

・乱雑なリストほどソートが速い。
・pivotの取り方によっては時間がかかることもある。

今回はpivotをリストの末項にしました。
（pop()で取り出したので、末項だと速そうだった）

python3

import random

def quick_sort(seq):
    if len(seq) <= 1:    #要素が1個だけのリストはそのまま返却
        return seq
    pivot = seq.pop()
    lower = [i for i in seq if i <= pivot]
    higher = [i for i in seq if i > pivot]
    return quick_sort(lower) + [pivot] + quick_sort(higher)

list1 =[random.randint(0,100) for i in range(10)]
print("original:",list1)
print("sorted  :",quick_sort(list1))

感想：
・再帰呼び出しは少しのミスでrecursionエラーがでてめんどくさい。
・ lower = [i for i in seq if i <= pivot]のところで、
　最初は<=のイコールを忘れていて、ソートすると要素が消失していた。
　→pivotと同一の値の要素があった場合に、大小どちらの集団にも入れず仲間外れに・・・
・入力が不正なリストでないかなどの判断はどこでやるのがいいんだろう。
　関数の最初で判断してエラーを返したりすると、再帰のたびに無駄な判断になりそう。

今後の改良点
・クイックソートはソートされている配列（エントロピーが低い？）に対して弱いので、何か対策を。
　あらかじめシャッフルするなど。
・大小の集団に分けるところで時間がかかっていそうなので、改良できるならする。
　higherのリストをpopで作る、要素どうしを交換するなど。