這應該是在python快速排序算法實現一些小錯誤

-2

我已經在python中實現快速排序算法，但是當我計算完成排序數組的交換次數它不能正確計算。我確信我正在犯一些非常愚蠢的錯誤，但我無法找到它。任何人都可以在這方面幫助我嗎？這是我所做的代碼。這應該是在python快速排序算法實現一些小錯誤

def partition(iArray, l, r): 
    count = 0 
    counta = 0 
    countb = 0 
    if len(iArray[l:r]) >= 1: 
     #print "\nInput Array : ",iArray 
     pivot = iArray[l] 
     #print "pivot:",pivot 
     j = l+1 
     i = l+1 
     while j <= r and j<len(iArray): 
      if iArray[j] < pivot: 
       (iArray[j],iArray[i]) = (iArray[i],iArray[j]) 
       i += 1 
      j += 1 
      #print "iArray : \t",iArray 
     (iArray[l],iArray[i-1]) = (iArray[i-1],iArray[l]) 
     #print "sorted array : ",iArray, " i:",i," j:",j," l:",l 
     count += iArray.index(pivot) 
     counta = partition(iArray,l,i-1) 
     countb = partition(iArray,i,j-1) 
    sum = count+counta+countb 
    return sum 

#------------------------------------- 

A = [56, 276, 68, 159, 68, 89, 245, 14, 45, 126, 78, 19, 15] 
l = 0     # Choosing pivot - as first element 
r = len(A) 
m = partition(A,l,r-1) 
print A[:] 
print m

此代碼打印的互換m個爲77，而對於定數組中的正確答案是32。

來源

2016-07-27 Sudhanshu Dixit

你是什麼意思「交換的正確數量」？你的數組是否被排序？ –

@JohnCarpenter：是的數組得到排序，但是當我計算交換次數時，它計算錯誤。 –

當總是選擇左側數據透視表時，我在該數組上進行了32次總比較。你確定你應該計算掉期嗎？ –

免責聲明：我沒有測試過這一點，但我相信我已經找到了幾個問題。

首先，它看起來像行

count += iArray.index(pivot)

是錯誤的，因爲該指數將是整個數組中的索引，而不僅僅是l和r之間。因此，改變這種

count += iArray.index(pivot) - l

然而，由於性能問題，不使用index()，因爲你已經有了指數！支點的代碼中的索引僅僅是i-1，所以樞軸的數量將i-l所以請使用可代替

count += i - l

最後，我不知道您的掉期基準數進來，但你可以改變我認爲以下兩行可以稍微改善你的表現。

變化if len(iArray[l:r]) >= 1:到if r-l >= 1:
因爲你知道，在指數i-1值在你的循環結束的支點，你沒有把它列入你的遞歸。這個想法是你的分支已經在分區結束時的正確位置。更改
```
counta = partition(iArray,l,i-1) 
countb = partition(iArray,i,j-1) 
```
到（該i-2是變化的）
```
counta = partition(iArray,l,i-2) 
countb = partition(iArray,i,j-1) 
```

來源

2016-07-28 14:36:19

謝謝你的指點約翰..當我下次編碼時，我會記住這些要點..！此外，你是正確的，要計算我應該計算I-I的掉期次數。通過將i-1更改爲i-2，結果是從不考慮最後一個元素進行比較。所以我猜這條線沒有改變。這說起來很尷尬，但是當我回過頭去再次回顧這個問題時，它說要計算比較次數。這不是交換次數，而是我尋找的比較次數。所以我會改變上面的問題。 –

不是改變這個問題，而是SO社區推薦的另一個問題:) –

你正在尋找的答案是比較的數量，而不是交換的數量。所以有兩個變化：

該行是不正確的，真的不計算比較的數量。

count += iArray.index(pivot)

由於比較次數在整個輸入數組完成的，它應該是

count += r-l-1
雖然調用分區第二時間在該行

countb = partition(iArray,i,j-1)

應該運行到第Ë陣列是「R」，因此該線將因此這些變化應該是能夠正確計算的比較次數後變爲

countb = partition(iArray,i,r)

。我很感謝'Kenny Ostrom'誰指出這一點，並讓我重新審視這個問題。所以，再次感謝Kenny。

來源

2016-07-28 17:22:33

這應該是在python快速排序算法實現一些小錯誤

回答

相關問題