實現快速排序CS50風格時發生IndexError

作爲編程相當新穎的人，我試圖在Python中實現快速排序。不過，我試圖用某種方式來實現它，這似乎並不是最常見的方式。我正在使用CS50中視頻中解釋的技巧：https://www.youtube.com/watch?v=aQiWF4E8flQ 實現快速排序CS50風格時發生IndexError

該版本的算法在數組末尾選擇一個透視圖，在開始處放置一個「牆」並開始迭代列表。當它找到一個比樞軸小的物品時，它會將該物品與牆右側的物品交換，並將牆壁向右移動一個位置。當所有物品與樞軸相比時，它將樞軸放在牆上，牆壁向右移動一個位置。這一直持續到牆壁位於陣列的末端。

到目前爲止，我想出了這一點：

def quicksort(alist): 
    quicksort_helper(alist) 
    print alist 

def quicksort_helper(alist): 
    wall = 0 
    while wall < (len(alist) - 1): 
     pivot = len(alist) - 1   
     for current in range(wall, pivot): 
      if alist[current] < alist[pivot]: 
       alist[current], alist[wall] = alist[wall], alist[current] 
       wall = wall + 1 
      alist[wall], alist[pivot] = alist[pivot], alist[wall] 
      wall = wall + 1

當我嘗試運行我一直有與牆壁和樞軸的數組索引問題的方案，因爲這是錯誤消息我我得到：

IndexError: list index out of range

我試了很多與索引，但我似乎無法弄清楚。

來源

2016-03-08 Johanna

請參閱您的代碼已正確格式化，可能會因爲錯誤的縮進 –

而提供失敗的輸入（並非算法正確，因爲[4,2,1,1,2] '被分類爲[[2，2，4，1，1]'）。 –

最後的，無條件的交換必須在'for current ...'循環之後。它在兩個分區之間插入數據透視表。當然，目前的代碼只是分區。您必須將快速排序應用到左側和右側的兩個分區。 –

Quicksort的工作原理是這樣的：您首先對您的數組進行分區，以便有三個子數組：左邊的數組包含所有小於關鍵點的元素，無需排序。中間的「數組」只是一個元素，即pivot *。正確的數組包含所有大於或等於主鍵的元素。

該樞軸現在已知處於其正確位置。然後您必須對左側和右側的子陣列進行排序。

分區是在牆的幫助下完成的。樞軸的位置是固定的;它總是最右邊的元素。然後，您用樞軸對每個元素進行配對，如果它較小，則將其移動到牆的左側。您必須將牆向右或向右移動以騰出空間。

在查看了所有元素後，您有三個子數組，但順序錯誤：左，右，中心。（牆是左右子陣列之間的障礙物。）爲了使其正確順序，請將元素與支點交換到牆的右側，但不要移動牆。這隻能在分區循環之後進行一次。（請注意，如果樞軸恰好是最大的元素，則將其與自身交換，這是可以的，如果浪費的話）。

您的算法使用0和數組的ength作爲邊界。這適用於整個陣列。當你想對子排列進行排序時，你必須調整這些界限。因此，將邊界傳遞給quicksort幫助程序是一個好主意，以便您可以遞歸。（這是自動設置的下限和上限排他性，正如索引len(a)超過a的有效索引範圍時索引從零開始。）

這裏是一個有效的解決方案：

def quicksort(alist): 
    quicksort_helper(alist, 0, len(alist)) 

def quicksort_helper(alist, l, r): 
    if l < r: 
     wall = l 

     pivot = r - 1 

     for current in range(wall, pivot): 
      if alist[current] < alist[pivot]: 
       alist[current], alist[wall] = alist[wall], alist[current] 
       wall = wall + 1 

     alist[wall], alist[pivot] = alist[pivot], alist[wall] 

     quicksort_helper(alist, l, wall) 
     quicksort_helper(alist, wall + 1, r)

*）有一個快速排序三路那組相同值的所有樞軸在一起，以提高快速排序的糟糕表現與只有幾個獨特的陣列元素。

來源

2016-03-08 17:25:37

行alist[wall], alist[pivot] = alist[pivot], alist[wall]執行，在某些情況下，wall值增加後導致len(alist)觸發IndexError。

您可以使用pdb調試您的代碼，在函數中添加行import pdb;pdb.set_trace()以跟蹤變量值。

來源

2016-03-08 17:12:07 Forge

實現快速排序CS50風格時發生IndexError

回答

相關問題