计算用于按 QuickSort 排序的比较次数，Python

Question

所以我有这段代码来计算在选择枢轴点的三种不同方式下通过 QuickSort 方法进行排序的比较次数。选择数组中的第一个元素；选择数组中的最后一个元素；选择第一个、中间（第 n 个元素，如果 len(array)=2n）和最后一个元素的中值。输入文件包含 1 到 10,000（含，无重复）之间的所有整数，未排序。
但是这段代码只正确输出了第一种情况的结果，而后两种情况的结果输出为零，我不知道是哪一部分造成的，请帮助！这是代码

from pathlib import Path
file_path = Path("c:/Users/M/Desktop/Al/")
inFile = open(file_path / "QuickSort.txt", 'r')
with inFile as f:
    lines = [x.split() for x in f]  # a list of lists
    f.close()

    tempList =  zip(*lines)           # a list of tuples := transposed lines
    tempList = list(tempList)
    tempList = tempList[0]      # a list of strings
    
    A = map(int,tempList)               # a list of integers
    


def choosePivot(alist,first,last,pivotID):
    if pivotID == 'first':
        pass
    
    if pivotID == 'last':
        (alist[first], alist[last]) = (alist[last], alist[first])
        
    elif pivotID == 'middle':
        mid = (last-first)//2 + first
        listTemp = [alist[first], alist[last], alist[mid]]
        listTemp.sort()
        if listTemp[1] == alist[first]:
            pivotIndex = first
        elif listTemp[1] == alist[last]:
            pivotIndex = last
        else:
            pivotIndex = mid
        (alist[first], alist[pivotIndex]) = (alist[pivotIndex], alist[first])
        
        
    
def partition(alist, first, last):
    pivotVal = alist[first] # initialise pivot as the first element
    leftmark = first+1
    for rightmark in range(first+1,last+1):
        if alist[rightmark] < pivotVal:
            (alist[leftmark],alist[rightmark]) = (alist[rightmark],alist[leftmark])
            leftmark = leftmark + 1
    (alist[leftmark-1],alist[first]) = (alist[first],alist[leftmark-1])

    return leftmark-1       # partition point := where pivot finally occupies
    
    
    
def quickSort(alist,first,last,pivotID):
    numComp = last -first
    if last <= first:
        return (alist, 0)
    else:
        choosePivot(alist,first,last,pivotID)
        splitpoint = partition(alist,first,last)
        (Lsorted,numCompL) = quickSort(alist, first, splitpoint-1, pivotID)
        (Rsorted,numCompR) = quickSort(alist, splitpoint+1, last, pivotID)
        numComp =  numComp + numCompL + numCompR
    return (alist, numComp)
    

def main(fileName):
    pivotList =  ['first', 'middle', 'last']
    
    for pivotID in pivotList:
        A = list(fileName)
        (A, n) = quickSort(A,0,len(A)-1,pivotID)
        print ("number of comparisons: %d", n)


    
if __name__ == '__main__':
        # unit test
#        main('test.txt')
        main(A)

Answer 1

那是因为 (A, n) = quickSort(A,0,len(A)-1,pivotID) 对列表进行了排序。第一个算法 return 的正确结果，后续 return 0 因为列表现在已经排序了。
为避免这种情况，请使用 copy = A[:] 创建主列表的副本，然后在每次迭代中传递一个新副本。像

def main(fileName):
    pivotList =  ['first', 'middle', 'last']
    mainList = list(filename)
    for pivotID in pivotList:
        A = mainList[:]
        (A, n) = quickSort(A,0,len(A)-1,pivotID)
        print ("number of comparisons: %d", n)

计算用于按 QuickSort 排序的比较次数，Python

Compute the number of comparisons used to sort the by QuickSort, Python

python

algorithm

quicksort