Python Quicksortデバッグ

Question

私はこのクイックソートを実装しましたが、修正できないバグがあるようです。

私が示した例の出力は答えに近いですが、いくつかのインデックスは正しく配置されていません。

---

def partition(array, pivot, start, end): 

    # move pivot to the end 
    temp = array[pivot] 
    array[pivot] = array[end] 
    array[end] = temp 

    i = start 
    j = end - 1 

    while(i < j): 

     # check from left for element bigger than pivot 
     while(i < j and array[end] > array[i]): 
      i = i + 1 
     # check from right for element smaller than pivot 
     while(i < j and array[end] < array[j]): 
      j = j - 1 

     # if we find a pair of misplaced elements swap them 
     if(i < j): 
      temp = array[i] 
      array[i] = array[j] 
      array[j] = temp 

    # move pivot element to its position 
    temp = array[i] 
    array[i] = array[end] 
    array[end] = temp 

    # return pivot position 
    return i 

def quicksort_helper(array, start, end): 
    if(start < end): 
     pivot = (start + end)/2 
     r = partition(array, pivot, start, end) 
     quicksort_helper(array, start, r - 1) 
     quicksort_helper(array, r + 1, end) 

def quicksort(array): 
    quicksort_helper(array, 0, len(array) - 1) 

array = [6, 0, 5, 1, 3, 4, -1, 10, 2, 7, 8, 9] 
quicksort(array) 
print array 

---

私は答えは明白であろうが、私はそれを見つけることができない気持ちを持っています。

所望の出力：

[-1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 

実際の出力：

[-1, 0, 2, 3, 1, 4, 5, 6, 7, 8, 9, 10] 

Answer 1

重要な修理はあなたがお互いに向かってIとJを行進インナーwhileループ、です。正しいピボット以外の要素を交換することが心配ならば、投稿したロジックは問題ありません。しかし、最初のループは私が中央にピボット要素を交換するための正しい値を有することを確実にするために

while(i <= j and array[end] > array[i]): 
     i = i + 1 

する必要があること。それ以外の場合、適切な位置の左に1つの要素をスワップすることができます。そのため、ソートが失敗します。

また、クリーナー、スワップのために、Pythonの複数の割り当てを使用することができます：はい、ゴム製のアヒルを取得しに行くと、それは仕事をやる

while(i < j): 

    # check from left for element bigger than pivot 
    while(i <= j and array[end] > array[i]): 
     i = i + 1 
    # check from right for element smaller than pivot 
    while(i < j and array[end] < array[j]): 
     j = j - 1 

    # if we find a pair of misplaced elements swap them 
    if(i < j): 
     array[i], array[j] = array[j], array[i]