Python中的快速排序比较计数器 [英] Quick Sort Comparison Counter in Python

问题描述

我有一个功能齐全的快速排序分区算法，并且我试图在每次比较中都适合一个计数器.这给了我一个挑战.关于在哪里放置此计数器的任何提示?

I have a fully functioning quick sort partitioning algorithm and I am trying to fit in a counter for every comparison made. This is giving me a challenge. Any hints as to where to put this counter?

def partition(mylist, start, end):
    pos = start
    for i in range(start, end):
        if mylist[i] < mylist[end]:
            mylist[i],mylist[pos] = mylist[pos],mylist[i]
            pos += 1
    mylist[pos],mylist[end] = mylist[end],mylist[pos]
    return pos

def quicksort(mylist, start, end, c):
    if start < end:
        pos = partition(mylist, start, end)
        c= c+ (len(mylist) -1    )   
        quicksort(mylist, start, pos - 1, c)
        c= c+ (len(mylist) -1    )       
        quicksort(mylist, pos + 1, end, c)
        c= c+ (len(mylist) -1    )


count = (0)
quicksort(x, 0, len(x)-1, count)

其中 x 是指整数列表

推荐答案

要进一步改善一些现有答案，除非您尝试使此尾部递归(无论如何对Quicksort都无效)，则不需要传递计数值.相反，您可以保持不变，即对分区的每次调用都返回其已执行的所有比较的计数，而对quicksort的每次调用均返回其已执行的所有分区或其中的任何递归调用的计数.

To improve further on some existing answers, unless you are trying to make this tail recursive (which doesn't work for quicksort anyways), you don't need to pass in the count value. Instead you can just maintain the invariant that each call to partition returns the count of all comparisons it has performed and each call to quicksort returns the count of all partitions that have been performed by it or any recursive calls within it.

另外，我们可以将quicksort的递归实现放入一个辅助函数中，并将其包装在一个仅包含一个列表的漂亮函数中，因此我们不必手动传递起始索引和结束索引.

Additionally, we can put the recursive implementation of quicksort into a helper function and wrap it in a nice function which only takes a list so we don't have to manually pass in the start and end indices.

执行此操作将为我们提供以下内容:

Implementing this gives us the following:

def _partition(mylist, start, end):
    count = 0
    pos = start
    for i in xrange(start, end):
        count += 1
        if mylist[i] < mylist[end]:
            mylist[i], mylist[pos] = mylist[pos], mylist[i]
            pos += 1
    mylist[pos], mylist[end] = mylist[end], mylist[pos]
    return pos, count

def _quicksort(mylist, start, end):
    count = 0
    if start < end:
        pos, count = _partition(mylist, start, end)        
        count += _quicksort(mylist, start, pos - 1)
        count += _quicksort(mylist, pos + 1, end)
    return count

def quicksort(mylist, start=None, end=None):
    if start is None:
        start = 0
    if end is None:
        end = len(mylist) - 1
    return _quicksort(mylist, start, end)

x = [2,3,1]
count = quicksort(x)
print x, count

这篇关于Python中的快速排序比较计数器的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！