クイックソートとPythonでの再帰

Question

私はPythonでquicksortを実装するために、2つの主要な関数--partitionとquicksortを使用しています。 パーティション関数は、pより大きい2つの配列を返すように設計されています。その後、クイックソートが別々に呼び出されます。 ので、クイックソートは、次のように動作します。

def quicksort(array) 
    pivot = 0 # pivot choice is irrelevant 
    left,right = partition(array,pivot) 
    quicksort(left) 
    quicksoft(right) 
    return left+right 

しかし、私の理解から、それだけで1つのインデックスを返すためにパーティションを設計することが可能でなければなりません - 区切り大きく、小さなアレイを、次のようにクイックソートを再設計：

def quicksort(array) 
    pivot = 0 # pivot choice is irrelevant 
    i = partition(array,pivot) 
    quicksort(array[:i-1]) 
    quicksoft(array[i:]) 
    return array 

は、しかし、この実装は、部分的にソートされた配列

original array [5, 4, 2, 1, 6, 7, 3, 8, 9] 
sorted array [3, 4, 2, 1, 5, 7, 6, 8, 9] 

を返す私はここで何をしないのですか？

Answer 1

あなたのコードを見ることなく、それは確かに難しいですが、一つの可能​​なエラーがi-1次のとおりです。

>>> [1,2,3,4][:2] 
[1, 2] 
>>> [1,2,3,4][2:] 
[3, 4] 

（あなたは、単にピボットをスキップすることができるが？）

また、スライスが新しいリストであります、ないビュー：

それはパイを作成しているため（典型的な機能プログラムは、くそ、すべてでクイックソートではありませんクイックソートをやって残念です

>>> l = [1,2,3,4] 
>>> l[2:][0] = 'three' 
>>> l 
[1, 2, 3, 4] 

ル新しいアレイのが）...あまりにも

私を悩ますあなたは、リスト全体プラスLO/HIインデックスを渡すことによって、第二の問題ラウンド作業することができます：

def quicksort(data, lo=0, hi=None): 
    if hi is None: hi = len(data) 
    .... 

Answer 2

quicksort(array[:i-1])は、実際には最初にクイックソートを呼び出すことはありません。配列の最初のパーティションのコピーに対してquicksortを呼び出します。したがって、あなたのコードは、配列を適切な場所に分割し、次に半分のコピーを作成してソートしようとしますが、結果の配列では何もしません。したがって、再帰呼び出しは効果がありません。

このようにしたい場合は、リストのコピーをスライスで作成するのではなく、関数全体に適用する範囲だけでなくリスト全体を渡す必要があります。

Answer 3

私は同じ問題を抱えていました。クイックソートは部分的にソートされたリストを返していました。問題は、自分の配列でピボットを返さないということでした。ピボットの配列を作成すると、再帰が適切に機能します。

ie。私のパーティション関数が返す代わりに：右

左

リターンは、それが左

リターン、pivotval、右