クイックソート：無限ループ

Question

QuickSort実行の次の実装無限ループに

def partition(arr, lo, hi): 
    pivot = lo 
    for i in range(lo+1, hi+1): 
     if arr[i] <= arr[lo]: 
      pivot += 1 
      arr[i], arr[pivot] = arr[pivot], arr[i] 
    arr[lo], arr[pivot] = arr[pivot], arr[lo] 
    return pivot 

def quickSort(arr, lo=0, hi=None): 
    if not hi: hi = len(arr) - 1 
    if lo >= hi: return 

    pivot = partition(arr, lo, hi) 
    quickSort(arr, lo, pivot-1) 
    quickSort(arr, pivot+1, hi) 


arr = [5,3,2,-9,1,6,0,-1,9,6,2,5] 
quickSort(arr) 
print(arr) 

私はpartition機能が犯人であると推定。間違いを理解することはできません。

ありがとうございました

Answer 1

問題がhiのための初期化コードである：

if not hi: hi = len(arr) - 1 

hiがゼロの場合の条件not hiはTrueです。

quicksort(arr, 0, 0)とquicksort(arr, 1, 0)（そのうちの1つはソートの過程でほとんど常に発生します）が、再帰の終了ではなく、ほとんどのリストのソートを再試行します。

if not hiではなく、より具体的なテストif hi is Noneを使用する必要があります。この方法では、hiがゼロであれば正しく再初期化されず、ユーザーが関数に渡されなかったため、hiがNoneの場合にのみ初期化コードが実行されます。

Answer 2

ループは決してパーティションのdefで動作しません。以下を参照してください

[5, 3, 2, -9, 1, 6, 0, -1, 9, 6, 2, 5] 
lo 0 hi 11 
pivot 8 
[5, 3, 2, -9, 1, 0, -1, 2, 5, 6, 6, 9] 
lo 0 hi 7 
pivot 7 
[2, 3, 2, -9, 1, 0, -1, 5, 5, 6, 6, 9] 
lo 0 hi 6 
pivot 5 
[-1, 2, -9, 1, 0, 2, 3, 5, 5, 6, 6, 9] 
lo 0 hi 4 
pivot 1 
[-9, -1, 2, 1, 0, 2, 3, 5, 5, 6, 6, 9] 
lo 0 hi 11 
pivot 0 
[-9, -1, 2, 1, 0, 2, 3, 5, 5, 6, 6, 9] 
lo 1 hi 11 

パーティションは、ジョブ全体を正しく実行しているようには見えませんが、2段階プロセスです。以下のサンプルパーティションdefを参照してください。また、あなたは元のソースhereを参照することができます。

def partition(alist,first,last): 
    pivotvalue = alist[first] 

    leftmark = first+1 
    rightmark = last 

    done = False 
    while not done: 

     while leftmark <= rightmark and alist[leftmark] <= pivotvalue: 
      leftmark = leftmark + 1 

     while alist[rightmark] >= pivotvalue and rightmark >= leftmark: 
      rightmark = rightmark -1 

     if rightmark < leftmark: 
      done = True 
     else: 
      temp = alist[leftmark] 
      alist[leftmark] = alist[rightmark] 
      alist[rightmark] = temp 

    temp = alist[first] 
    alist[first] = alist[rightmark] 
    alist[rightmark] = temp 


    return rightmark