这应该是在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快速排序算法实现一些小错误

回答

相关问题