如何按照可汗学院的示例修复此迭代快速排序实现的征服步骤？

Question

出于教育目的，我正在尝试学习快速排序算法。我没有在 Web 上查看实现或尝试直接从 wikipedia 上的伪代码实现，而是尝试 "hard way" 方法。

我从 CS50 https://www.youtube.com/watch?v=aQiWF4E8flQ&t=305s 看了这个讲座，以了解数字在 "quick sorted" 时是如何移动的。我将在下面展示的实现非常适合视频中提供的示例。初始未排序数组的视频示例是这样的：

这是我在 Python 3:

中的代码

len_seq = int(input())

print("len_seq",len_seq)

seq_in = list(map(int,(input()).split()))

print("seq_in",seq_in)

def my_quick_sort(seq):

    wall_index = 0

    pivot_corect_final_index_list = [] 

    while wall_index<len_seq:

        pivot = seq[-1]
        print("pivot",pivot)

        print("wall_index",wall_index)

        for i in range(wall_index,len_seq):
            print ("seq[i]",seq[i])
            if seq[i]<pivot:
                print("before inside swap,", seq)
                seq[wall_index],seq[i]=seq[i],seq[wall_index]
                print("after inside swap,", seq)
                wall_index = wall_index + 1
                print ("wall_index",wall_index)

        print("before outside swap,", seq)

        seq[wall_index],seq[-1]=seq[-1],seq[wall_index]
        print("after outside swap,", seq)

        pivot_corect_final_index = wall_index
        print ("pivot correct final index",pivot_corect_final_index)

        pivot_corect_final_index_list.append(pivot_corect_final_index)
        print ("pivot_corect_final_index_list",pivot_corect_final_index_list)

        wall_index = wall_index + 1
        print ("wall_index",wall_index)


    return seq

print(my_quick_sort(seq_in))

要在我的代码中使用哈佛大学的 CS50 示例，您需要输入：

9
6 5 1 3 8 4 7 9 2

算法运行良好，returns正确输出：

[1, 2, 3, 4, 5, 6, 7, 8, 9]

继续学习，我尝试实现可汗学院的示例：https://www.khanacademy.org/computing/computer-science/algorithms/quick-sort/a/overview-of-quicksort

本例中的未排序列表为：

[9, 7, 5, 11, 12, 2, 14, 3, 10, 6]

您需要在我的代码中输入以下内容才能运行它：

10
9 7 5 11 12 2 14 3 10 6

与哈佛示例不同，在这种情况下，我的实现无法完美运行。它returns:

[5, 2, 3, 6, 7, 9, 10, 11, 12, 14]

如您所见，我视为枢轴的所有数字都在正确的位置结束。但是，枢轴后面的一些数字不正确。

阅读可汗学院的文章，似乎我的实现在分区步骤上是正确的。但是，它在征服步骤上是不正确的.我试图避免寻求最终解决方案。我正在努力改进我目前所构建的内容。不确定这是否是最好的方法，但这就是我现在正在尝试的方法。

如何修复征服步骤？是否有必要引入递归方法？我怎样才能在内部我正在进行的迭代过程中做到这一点？是否应该在成功处理每个枢轴后引入该步骤？

感谢您耐心阅读这么长post。

Answer 1

无法评论，信誉度不够

在算法的第一遍中，您正确地将所有小于主元的元素放在了主元的左侧。但是，由于 wall_index 的值增加（例如从 0 到 1），您忽略了索引为 0 的最左边的元素（它可能不在正确的位置，因此不应忽略）。

在可汗学院测试用例中，数字 5 在第一遍中被放置在最左边的索引处，然后被后续遍忽略，因此它卡在了左边。同样，尝试修改哈佛示例

9
6 5 1 3 8 4 7 2 9

产量

[6, 5, 1, 3, 8, 4, 7, 2, 9]

第一次分区后，您必须确保将快速排序应用于主元左侧和右侧的数组。例如，在第一个枢轴 (6) 放置在 Khan 示例的正确位置后（您标记为外部交换），

[5, 2, 3, 6, 12, 7, 14, 9, 10, 11]
 <--1-->  p  <--------2--------->

您必须对上图中的子数组 1 和 2 应用相同的快速排序。我建议你先尝试递归实现，这会让你对算法有一个很好的了解，然后尝试迭代实现它。

如何按照可汗学院的示例修复此迭代快速排序实现的征服步骤？

How to fix the Conquer step of this iterative quicksort implementation following Khan Academy's example?

algorithm

quicksort

divide-and-conquer

python-3.x