QuickSort with Pivot Function 问题？

Question

过去几个小时我一直在看这个，但仍然不明白我哪里搞砸了。我不断收到如下所示的索引越界错误：

我所做的每一个小的编辑或更改，都会运行我陷入另一个错误，然后我在尝试简化我的代码后回到这里。

def quickSort(alist):
    firstList = []
    secondList = []
    thirdList = []

    if(len(alist) > 1):
        #pivot = pivot_leftmost(alist)
        #pivot = pivot_best_of_three(alist)
        pivot = pivot_ninther(alist)
        #pivot = pivot_random(alist)

        for item in alist:
            if(item < pivot):
                firstList.append(item)
            if(item == pivot):
                secondList.append(item)
            if(item > pivot):
                thirdList.append(item)
        sortedList = quickSort(firstList) + secondList + quickSort(thirdList)
        return sortedList
    else:
        print("list:", alist)
        print("sorted, nothing to do") #debug
        print("") #debug
        return alist

def pivot_ninther(alist):
    listLength = int(len(alist))
    third = int(listLength / 3)

    leftList = alist[:third]
    midlist = alist[third:(third * 2)]
    lastlist = alist[(third * 2):(third * 3)]

    leftBest = pivot_best_of_three(leftList)
    midBest = pivot_best_of_three(midlist)
    lastBest = pivot_best_of_three(lastlist)

    pivots = [leftBest, midBest, lastBest]

    return pivot_best_of_three(pivots)

我很确定新人可以很容易地找到它，但我已经看了好几个小时了。谢谢！

更新：（我的 Best_of_three 函数）

def pivot_best_of_three(alist):
    leftmost = 0
    middle = int(len(alist) / 2)
    rightmost = len(alist) - 1

    if (alist[leftmost] <= alist[middle] <= alist[rightmost] or alist[rightmost] <= alist[middle] <= alist[leftmost]):
        return alist[middle]
    elif (alist[middle] <= alist[leftmost] <= alist[rightmost] or alist[rightmost] <= alist[leftmost] <= alist[middle]):
        return alist[leftmost]
    else:
        return alist[rightmost]

Answer 1

尝试较小的计数 (<= 20) 并检查当 third == 0 时 pivot_ninther() 中发生了什么（在递归的最深层次）？似乎它会创建空数组，然后尝试对它们进行索引。

代码应在调用 pivot_ninther() 之前检查以确保长度 >= 9，然后如果调用 ...best_of_three() 则 >= 3。如果只有一两个项目，选择一个。

建议，在快速排序工作后，备份源代码而不是创建新数组，枢轴函数应该与原始数组和第一个/中间/最后一个索引一起使用。

您可以使用交换来简化寻找 3 的中位数的过程。这将有助于从逆序数组开始的情况。

    // median of 3
    i = lo, j = (lo + hi)/2, k = hi;
    if (a[k] < a[i])
        swap(a[k], a[i]);
    if (a[j] < a[i])
        swap(a[j], a[i]);
    if (a[k] < a[j])
        swap(a[k], a[j]);
    pivot = a[j];

维基文章：

http://en.wikipedia.org/wiki/Quicksort#Choice_of_pivot

Answer 2

当 pivot_best_of_three 试图找到零项列表的 rightmost 成员时，会出现 IndexError。解决这个问题的简单方法就是不要将此类列表传递给它。 :)

以下是这些函数的略微修改版本。我已经用各种长度的列表测试了这些版本，直到长度为零，它们似乎都能正常运行。

def pivot_ninther(alist):
    listLength = len(alist)
    if listLength < 3:
        return alist[0]

    third = listLength // 3
    leftList = alist[:third]
    midlist = alist[third:-third]
    lastlist = alist[-third:]

    leftBest = pivot_best_of_three(leftList)
    midBest = pivot_best_of_three(midlist)
    lastBest = pivot_best_of_three(lastlist)

    pivots = [leftBest, midBest, lastBest]

    return pivot_best_of_three(pivots)

def pivot_best_of_three(alist):
    leftmost = alist[0]
    middle = alist[len(alist) // 2]
    rightmost = alist[-1]

    if (leftmost <= middle <= rightmost) or (rightmost <= middle <= leftmost):
        return middle
    elif (middle <= leftmost <= rightmost) or (rightmost <= leftmost <= middle):
        return leftmost
    else:
        return rightmost

如您所见，我已经简化了 pivot_best_of_three，因此它不会为同一值多次索引 alist。

但可以通过使用简单的 sorting network:

进一步简化

def sort3(a, b, c):
    if c < b: b, c = c, b
    if b < a: a, b = b, a
    if c < b: b, c = c, b
    return a, b, c

def pivot_best_of_three(alist):
    leftmost = alist[0]
    middle = alist[len(alist) // 2]
    rightmost = alist[-1]
    return sort3(leftmost, middle, rightmost)[1]

QuickSort with Pivot Function 问题？

QuickSort with Pivot Function issue?

python

sorting

algorithm

quicksort