Python によるクイックソート
実際には、Python が提供する組み込みの並べ替えを常に使用する必要があります。ただし、クイックソートアルゴリズムを理解することは有益です。
ここでの私の目標は、参考資料に戻らなくても、読者が簡単に理解して複製できるように、主題を分解することです。
クイックソート アルゴリズムは基本的に次のとおりです。
- ピボット データ ポイントを選択します。
- ピボットよりも小さい (下の) すべてのデータ ポイントをピボットの下の位置に移動します。ピボット以上 (上) のデータ ポイントを上の位置に移動します。
- ピボットの上下の領域にアルゴリズムを適用する
データがランダムに分布している場合、最初のデータ ポイントをピボットとして選択することは、ランダムな選択と同じです。
読みやすい例:
まず、コメントと変数名を使用して中間値を指す読みやすい例を見てみましょう。
def quicksort(xs):
"""Given indexable and slicable iterable, return a sorted list"""
if xs: # if given list (or tuple) with one ordered item or more:
pivot = xs[0]
# below will be less than:
below = [i for i in xs[1:] if i < pivot]
# above will be greater than or equal to:
above = [i for i in xs[1:] if i >= pivot]
return quicksort(below) + [pivot] + quicksort(above)
else:
return xs # empty list
ここで示したアルゴリズムとコードを言い換えると、ピボットの上の値を右に移動し、ピボットの下の値を左に移動してから、それらのパーティションを同じ関数に渡してさらに並べ替えます。
ゴルフ:
これは 88 文字までゴルフできます。
q=lambda x:x and q([i for i in x[1:]if i<=x[0]])+[x[0]]+q([i for i in x[1:]if i>x[0]])
どのようにそこにたどり着くかを確認するには、まず読みやすい例を取り上げ、コメントとドキュメント文字列を削除し、その場でピボットを見つけます。
def quicksort(xs):
if xs:
below = [i for i in xs[1:] if i < xs[0]]
above = [i for i in xs[1:] if i >= xs[0]]
return quicksort(below) + [xs[0]] + quicksort(above)
else:
return xs
次に、インプレースで以下を見つけます。
def quicksort(xs):
if xs:
return (quicksort([i for i in xs[1:] if i < xs[0]] )
+ [xs[0]]
+ quicksort([i for i in xs[1:] if i >= xs[0]]))
else:
return xs
これで、andfalse の場合は前の要素が返されることがわかり、true の場合は次の要素が評価されて返されます。
def quicksort(xs):
return xs and (quicksort([i for i in xs[1:] if i < xs[0]] )
+ [xs[0]]
+ quicksort([i for i in xs[1:] if i >= xs[0]]))
ラムダは単一の式を返し、単一の式に簡略化したため (読みづらくなっていますが)、ラムダを使用できるようになりました。
quicksort = lambda xs: (quicksort([i for i in xs[1:] if i < xs[0]] )
+ [xs[0]]
+ quicksort([i for i in xs[1:] if i >= xs[0]]))
この例に合わせて、関数名と変数名を 1 文字に短縮し、不要な空白を削除します。
q=lambda x:x and q([i for i in x[1:]if i<=x[0]])+[x[0]]+q([i for i in x[1:]if i>x[0]])
このラムダは、ほとんどのコード ゴルフと同様に、かなり悪いスタイルであることに注意してください。
Hoare パーティショニング スキームを使用したインプレース クイックソート
以前の実装では、多くの不要な余分なリストが作成されます。これをインプレースで行うことができれば、スペースの無駄遣いを避けることができます。
以下の実装では、ウィキペディアで詳細を読むことができる Hoare パーティショニング スキームを使用しています(ただしpartition()、do-while の代わりに while-loop セマンティクスを使用し、縮小ステップを最後に移動することで、呼び出しごとに最大 4 つの冗長な計算を削除したようです)。外側の while ループ)。
def quicksort(a_list):
"""Hoare partition scheme, see https://en.wikipedia.org/wiki/Quicksort"""
def _quicksort(a_list, low, high):
# must run partition on sections with 2 elements or more
if low < high:
p = partition(a_list, low, high)
_quicksort(a_list, low, p)
_quicksort(a_list, p+1, high)
def partition(a_list, low, high):
pivot = a_list[low]
while True:
while a_list[low] < pivot:
low += 1
while a_list[high] > pivot:
high -= 1
if low >= high:
return high
a_list[low], a_list[high] = a_list[high], a_list[low]
low += 1
high -= 1
_quicksort(a_list, 0, len(a_list)-1)
return a_list
十分にテストしたかどうかわかりません：
def main():
assert quicksort([1]) == [1]
assert quicksort([1,2]) == [1,2]
assert quicksort([1,2,3]) == [1,2,3]
assert quicksort([1,2,3,4]) == [1,2,3,4]
assert quicksort([2,1,3,4]) == [1,2,3,4]
assert quicksort([1,3,2,4]) == [1,2,3,4]
assert quicksort([1,2,4,3]) == [1,2,3,4]
assert quicksort([2,1,1,1]) == [1,1,1,2]
assert quicksort([1,2,1,1]) == [1,1,1,2]
assert quicksort([1,1,2,1]) == [1,1,1,2]
assert quicksort([1,1,1,2]) == [1,1,1,2]
結論
このアルゴリズムは、コンピュータ サイエンスのコースで頻繁に教えられ、就職の面接でも求められます。再帰と分割統治について考えるのに役立ちます。
Python では、組み込みのtimsortアルゴリズムが非常に効率的であり、再帰の制限があるため、 Quicksortはあまり実用的ではありません。list.sortでリストをその場でソートするか、 で新しいソート済みリストを作成することを期待しますsorted- どちらもkeyandreverse引数を取ります。