algorithm - 使用堆栈的快速排序实现

Question

我正在阅读以下链接中使用堆栈的快速排序实现。

link

我的问题是关于下面的段落。

The policy of putting the larger of the small subfiles on the stack ensures that each entry on the stack is no more than one-half of the size of the one below it, so that the stack needs to contain room for only about lg N entries. This maximum stack usage occurs when the partition always falls at the center of the file. For random files, the actual maximum stack size is much lower; for degenerate files it is likely to be small.

This technique does not necessarily work in a truly recursive implementation, because it depends on end- or tail-recursion removal. If the last action of a procedure is to call another procedure, some programming environments will arrange things such that local variables are cleared from the stack before, rather than after, the call. Without end-recursion removal, we cannot guarantee that the stack size will be small for quicksort.

1. 作者所说的“堆栈中的每个条目不超过其下方条目大小的二分之一”是什么意思？能否请您举个例子。

2. 作者是如何得出堆栈只需要大约 lg N 个条目的空间的结论的？

3. authore 是什么意思“如果不删除末端递归，我们不能保证快速排序的堆栈大小会很小”？

感谢您的宝贵时间和帮助。

Answer 1

The policy of putting the larger of the small subfiles on the stack ensures that each entry on the stack is no more than one-half of the size of the one below it,

事实并非如此。假设您要对一个包含 100 个元素的数组进行排序，并且第一个主元恰好位于中间。然后你有一个堆栈

49
50

然后将 49 个元素的部分从堆栈中弹出，分区，然后将两个部分压入堆栈。假设这次枢轴的选择不太好，有 20 个不大于枢轴的元素。然后你会得到堆栈

20
28
50

并且每个堆栈条目都超过下面一个的一半。

但这不可能永远持续下去，我们已经

During the entire sorting, if stack level k is occupied, its size is at most total_size / (2^k).

当排序开始时，这显然是正确的，因为那时堆栈上只有一个元素，在第 0 层，这是大小为 total_size 的整个数组。 .

现在，假设进入循环 (while(!stack.empty())) 时声明的属性成立。

长度为 s 的子数组从堆栈级别弹出 m .如果s <= 1 ，在下一次循环迭代之前什么都不做，不变量继续成立。否则，如果 s >= 2 , 分区之后，有两个新的子数组要压入栈中，s-1元素在一起。这两个中较小的一个大小为 smaller_size <= (s-1)/2 , 较大的尺寸为 larger_size <= s-1 .堆栈级别 m将被两者中较大的一个占据，我们有

larger_size  <= s-1 < s <= total_size / (2^m)
smaller_size <= (s-1)/2 < s/2 <= total_size / (2^(m+1))

对于堆栈级别 m分别m+1在循环体的末尾。不变量在下一次迭代中成立。

由于堆栈中最多有一个大小为 0 的子数组(然后在下一次迭代中立即将其弹出)，因此永远不会超过 lg total_size + 1栈层被占用。

关于

What does author mean by "Without end-recursion removal, we cannot guarantee that the stack size will be small for quicksort" ?

在递归实现中，您可以进行深度递归，并且当堆栈帧未被重新用于结束调用时，您可能需要线性堆栈空间。考虑一个愚蠢的主元选择，总是选择第一个元素作为主元，以及一个已经排序的数组。

[0,1,2,3,4]

分区，主元在位置 0，较小的子数组为空。递归调用更大的子数组 [1,2,3,4] , 分配一个新的栈帧(所以现在有两个栈帧)。同理，接下来用子数组递归调用[2,3,4]分配第三个堆栈帧等。

如果有结束递归删除，即堆栈帧被重用，则与上面的手动堆栈有相同的保证。