具有两个指针的快速排序算法

Question

你能帮我完成这个任务吗？来自 R. Sedgewick 的 "Introduction INTRODUCTION ТО PROGRAMMING IN PYTHON Ап lnterdisciplinary Approach"

Partitioning. Compose a function that sorts an array that is known to have at most two different values. Hint: Maintain two pointers, one starting at the left end and moving right, and the other starting at the right end and moving left. Maintain the invariant that all elements to the left of the left pointer are equal to the smaller of the two values and all elements to the right of the right pointer are equal to the larger of the two values.

所以我想到了这个，但它不起作用。我哪里错了？我相信这是在两个 quickSort2 方法被调用时引起的（我在那里添加了一些评论）。

import sys      

def quickSort2(arr, left, right, n, direction):
    if n == 1:
        return
    if left > right:
        return
    if left == right:
        print ("left ")
        print([i for i in arr[len(arr)-n:left]])
        print ("right ")
        print([i for i in arr[left+1:len(arr)]])
        print ("pivot ")
        print(arr[left])

        quickSort2(arr, len(arr)-n, left-1, left-len(arr)+n, True) # Is this ok?
        quickSort2(arr, left+1, len(arr)-1, len(arr)-left-1, True) # Is this ok?

        return
    if direction:
        if arr[left] < arr[right]:
            quickSort2(arr, left+1, right, n, True)
        #elif arr[left] > arr[right]:
        else:
            arr[left], arr[right] = arr[right], arr[left]
            quickSort2(arr, left, right-1, n,  False)
    else:
        if arr[left] < arr[right]:
            quickSort2(arr, left, right-1, n,  False)
        #elif arr[left] > arr[right]:
        else:
            arr[left], arr[right] = arr[right], arr[left]
            quickSort2(arr, left+1, right, n, True)



if __name__ == "__main__":
    #array = [5,4,5,4]
    #array = [5,4,5,4,4,5,4]
    #array = [5,5,4,5,5,5,5,4,5,5,4,5,4,4,4,4,4,4,5,5,4,5,4]
    array = [5,4,4,1,7,4,3,8,3,1]

    quickSort2(array, 0, len(array) - 1, len(array),  True)
    for i in array: print (i, end = " ")

例如数组 = [5,5,4,5,5,5,5,4,5,5,4,5,4,4,4,4,4,4,5,5 ,4,5,4] 它 returns

4 4 4 4 4 4 4 4 4 4 5 4 5 5 5 5 5 5 5 5 5 5 5

Answer 1

这个问题并不要求你实现一个快速排序算法，它只是要求你划分一个列表，该列表最多有 两个不同的值。提示中的重要一点是：

Maintain the invariant that all elements to the left of the left pointer are equal to the smaller of the two values and all elements to the right of the right pointer are equal to the larger of the two values.

这就是您的算法无法保证的。让我们看看您的示例案例：如果左右索引都指向 5 并且您当前的方向是从右到左，会发生什么情况。 if 子句将被执行：

arr[left], arr[right] = arr[right], arr[left]
quickSort2(arr, left+1, right, n, True)

因此您交换了值（这没有效果，因为它们相等）并将 left 索引递增 1。这就是问题所在，您违反了不变量：左指针左侧有一个 5。

我建议删除 direction，因为不需要它并添加两个新变量，较小的值和较大的值。通过这样做，您始终知道您是否可以继续前进，或者指针是否应该停留在其当前索引处。

我还将该函数重命名为 partition，因为这更适合练习。

def partition(arr, smaller, larger, left, right, n):
    if left >= right:
        # the two pointers met, the array is partitioned
        return
    if arr[left] == smaller:
        # move left pointer to the right
        partition(arr, smaller, larger, left+1, right, n)
    elif arr[right] == larger:
        # move right pointer to the left
        partition(arr, smaller, larger, left, right-1, n)
    else:
        # when we find a larger on the left and a smaller on the right, we swap
        arr[left], arr[right] = arr[right], arr[left]
        # and move both pointers forward
        partition(arr, smaller, larger, left+1, right-1, n)

具有两个指针的快速排序算法

Quick Sort algorithm with two pointers

python

quicksort