快速排序分析和行为

Question

我正在阅读名为算法第 4 版 Robert Sedgewick 的书中有关快速排序算法的内容。

Quicksort is popular because it is not difficult to implement, works well for a variety of different kinds of input data, and is substantially faster than any other sorting method in typical applications. The quicksort algorithm’s desirable features are that it is in-place (uses only a small auxiliary stack) and that it requires time proportional to N log N on the average to sort an array of length N. None of the algorithms that we have so far considered combine these two properties.

Furthermore, quicksort has a shorter inner loop than most other sorting algorithms, which means that it is fast in practice as well as in theory. Its primary drawback is that it is fragile in the sense that some care is involved in the implementation to be sure to avoid bad performance.

我对以上文字的问题是

作者所说的"uses only a small auxiliary stack"是什么意思？
作者所说的"quicksort has a shorter inner loop than most other sorting algorithms"是什么意思？

要求以简单的例子进行说明。

谢谢

Answer 1

1 What does author mean by "uses only a small auxiliary stack" ?

作者的意思是除了要排序的数据外，只需要很少的额外内存。因此，排序期间生成的数据结构不会产生很大的开销。

What does author mean by "quicksort has a shorter inner loop than most other sorting algorithms" ?

作者的意思是在最内层循环中执行的指令数量是相当可观的，这对于例如。 cpu 缓存。

在下面的代码中，在内部循环中只有一个索引是 incremented/decremented。并且检查了循环条件。

举个例子我拿wikipedia

中提到的实现

algorithm quicksort(A, lo, hi) is
    if lo < hi then
        p := partition(A, lo, hi)
        quicksort(A, lo, p – 1)
        quicksort(A, p + 1, hi)

algorithm partition(A, lo, hi) is
pivot := A[lo]
i := lo – 1
j := hi + 1
loop forever
    do
        i := i + 1
    while A[i] < pivot
    do
        j := j – 1
    while A[j] > pivot
    if i >= j then
        return j
    swap A[i] with A[j]

Answer 2

function QuickSort(Array, Left, Right)
var
  L2, R2, PivotValue
begin
 Stack.Push(Left, Right);       // pushes Left, and then Right, on to a stack
 while not Stack.Empty do
 begin
     Stack.Pop(Left, Right);    // pops 2 values, storing them in Right and then Left
     repeat
         PivotValue := Array[(Left + Right) div 2];
         L2 := Left;
         R2 := Right;
         repeat
             while Array[L2] < PivotValue do // scan left partition
                 L2 := L2 + 1;
             while Array[R2] > PivotValue do // scan right partition
                 R2 := R2 - 1;
             if L2 <= R2 then
             begin
                 if L2 != R2 then
                     Swap(Array[L2], Array[R2]);  // swaps the data at L2 and R2
                 L2 := L2 + 1;
                 R2 := R2 - 1;
             end;
         until L2 >= R2;
         if R2 - Left > Right - L2 then // is left side piece larger?
         begin
             if Left < R2 then
                 Stack.Push(Left, R2);
             Left := L2;
         end;
         else
         begin
             if L2 < Right then // if left side isn't, right side is larger
                 Stack.Push(L2, Right);
             Right := R2;
         end;
     until Left >= Right;
 end;
 end;

What does author mean by "uses only a small auxiliary stack" ?

您不需要第二个数组来存储（如合并排序）它是在同一内存中计算的

What does author mean by "quicksort has a shorter inner loop than most other sorting algorithms" ?

快速排序中非常快的部分是内部循环（//扫描左分区和//扫描右分区）因为它只是在增加和支票...而不是更多。

Answer 3

作者所说的 "uses only a small auxiliary stack" 是什么意思？

您还需要考虑 quick-sort 是 in-place 排序算法。

in-place 表示：

此 in-place 功能大大减少了存储需求。
它使用恒定数量的存储（读取：固定数量的额外变量）来促进排序过程。

因此，由于存储量小且固定，故称quick-sort "uses only a small auxiliary stack"。

作者"quicksort has a shorter inner loop than most other sorting algorithms"是什么意思？

这可能意味着内部循环内的逻辑很简单，因此需要的代码更少。此 "shorter inner loop" 不应与循环迭代次数混淆。因为在递归树的任何级别上，迭代总数将仅为 "n"。

Answer 4

1 What does author mean by "uses only a small auxiliary stack" ?

理想情况下，快速排序在栈上使用O(log2(n))space，在最坏情况下，在栈上使用O(n)space，占用space 多于正在排序的数组。

What does author mean by "quicksort has a shorter inner loop than most other sorting algorithms" ?

这在现代系统上可能无关紧要，因为任何大小合理的内部循环都适合大多数处理器的代码缓存。条件分支会影响管道性能，具体取决于分支预测。

quicksort ... is substantially faster than any other sorting method in typical applications.

这不是真的，在最好的情况下快速排序只比合并排序快一点（不到 10%），而在最坏的情况下慢得多，O(n^2) 与 O( n 日志 (n))。合并排序的主要问题是它需要一个大小相同或原始数组大小 1/2 的临时数组。

快速排序分析和行为

quick sort analysis and behaviour

sorting

algorithm

quicksort