python: 快速排序调试

Question

我正在尝试实施快速排序，但我无法确定为什么会看到此错误。我正在递归调用排序 fn，后者又调用分区 fn。

错误：

[5, 2, 1, 6, 3, 89, 7869, 190, 3, 4, 5, 67]
[5, 2, 1, 6, 3, 5, 4, 3, 67, 7869, 89, 190]
[5, 2, 1, 6, 3, 5, 4, 3, 67, 7869, 89, 190]
[5, 2, 1, 6, 3, 5, 4, 3, 67, 89, 190, 7869]
[5, 2, 1, 6, 3, 5, 4, 3, 67]
Traceback (most recent call last):
  File "ch13.py", line 30, in <module>
    print(sort(A, L, R))
  File "ch13.py", line 22, in sort
    sort(A[:pivot_idx - 1], 0 , pivot_idx - 1)
  File "ch13.py", line 21, in sort
    pivot_idx =  partition(A, L, R)
  File "ch13.py", line 9, in partition
    while A[R] > pivot:
IndexError: list index out of range

实施：

def partition(A, L, R):
    # taking pivot as mosr right-element of array
    print(A)
    pivot = A[-1]
    pivot_index = len(A) - 1
    while True:
        while A[L] < pivot:
            L = L + 1
        while A[R] > pivot:
            R = R - 1
        if L >= R:
            break
        A[L], A[R] = A[R], A[L]
        L = L + 1
    A[pivot_index], A[L] = A[L], A[pivot_index]
    print(A)
    return L

def sort(A, L, R):
    if len(A)<=1: return
    pivot_idx =  partition(A, L, R)
    sort(A[:pivot_idx - 1], 0 , pivot_idx - 1)
    sort(A[pivot_idx - 1 :], pivot_idx + 1, R)
    return A

A = [5,2,1,6,3,89,7869,190,3,4,5,67]
L = 0
R = len(A) - 2
partition(A, L, R)
print(sort(A, L, R))

如果可能，请解释您的修复并指出我做错的地方。

Answer 1

该代码是 Hoare 分区方案的变体，其中主元和任何等于主元的元素可以在分区步骤后的任何位置结束，因此不应使用交换 A[pivot_index], A[L] = A[L], A[pivot_index]。返回的只是一些“中点”索引，其中元素 <= 枢轴位于左侧，元素 >= 枢轴位于右侧，元素 == 枢轴位于两侧。实现一个 post 增量更简单 | post 通过在快速排序函数中包含分区代码并使用两个索引来减少 Hoare 的变化：

void QuickSort(int *a, int lo, int hi)
{
int i, j;
int p, t;
    if(lo >= hi)
        return;
    p = a[lo + (hi-lo)/2];    // for python use: // 2 for integer divide
    i = lo;
    j = hi;
    while (i <= j){
        while (a[i] < p)i++;
        while (a[j] > p)j--;
            if (i > j)
                break;
            t = a[i];         // swap a[i], a[j]
            a[i] = a[j];
            a[j] = t;
            i++;
            j--;
    }
    QuickSort(a, lo, j);
    QuickSort(a, i, hi);      // i = (a[i] == p) ? j+2 : j+1
}

python: 快速排序调试

python: quicksort debugging

python

quicksort