0

我在为快速排序算法的某些实现定义和证明循环不变量时遇到了麻烦。这既不是 Lomuto 也不是 Hoare 的分区版本。

如果您知道以这种方式实现的某些已知版本的 Quicksort，请告诉我。

算法在 Python 中的实现：

def partition(arr: list, p: int, r: int):
    y = arr[p]
    i = p
    j = r + 1

    while i < j:
        i = i + 1

        while i <= r and A[i] < y:
            i = i + 1

        j = j - 1

        while j >= p and A[j] > y:
            j = j - 1

        if i <= j:
            swap(arr, i, j)

    swap(arr, j, p)

    return j


def quicksort(arr: list, p: int, r: int):
    if p < r:
        q = partition(arr, p, r)
        quicksort(arr, p, q - 1)
        quicksort(arr, q + 1, r)


def swap(arr: list, i, j):
    tmp = arr[i]
    arr[i] = arr[j]
    arr[j] = tmp

我设法定义了以下循环不变量（它可能不正确）：

在循环的每次迭代开始时，对于arraywhile中的每个索引：kA

  • 如果k = p，那么A[k] = y

  • 如果p < k <= i，那么A[k] < y

  • 如果j <= k <= r，那么A[k] > y

请帮我为方法中的while循环定义一个循环不变量partition()（如果上面不正确的话），并证明它。

4

1 回答 1

0

外while的不变量表示在到目前为止已经扫描的数组部分中，即范围A[p..i]和A[j..r]中，左侧元素不大于枢轴，右侧元素不小于。（当然，A的内容是初始内容的排列。）

当循环退出时，所有左边的元素不大于所有右边的元素，因此A[p..r]被分区。

于 2019-03-30T17:37:47.560 回答