Day-9 Divide-and-Conquer-4 : Quicksort, 随机化Quicksort

Quicksort- Tony Hoare - 1962

和merge-sort一样，他使用了Divide and conquer的想法，下面是对於一个阵列进行快速排序的三步分治过程

• Divide : 在阵列中找到一个元素，把这个元素作为基准点，将阵列拆分成两个子阵列，中每一个元素皆小於等於，中每一个元素皆大於等於。
• Conquer : 通过递回呼叫Quicksort，对和进行排序。
• Combine : 因为子阵列都是在原阵列中进行排序，就如同插入排序法一样，所以不需要合并。

QUICKSORT(A, low ,high)
    if low < high
        q = PARTITION(A, low, high)
        QUICKSORT(A, low, q-1)
        QUICKSORT(A, q+1, high)

为了排序A阵列中所有元素，一开始呼叫QUICKSORT(A, 1, A.lenght)

接着开始拆分阵列，这也是Quicksort的关键步骤

PARTITION(A, low, high)
    pivot = A[high]
    i = low - 1
    for j = low to high - 1
        if A[j] <= pivot
            i = i + 1
            exchange A[i] with A[j]
    exchangeA[i + 1] with A[high]
    return i + 1

选取一个pivot，也就是基准点，以他为基准进行阵列的拆分，程序进行的过程中会将阵列拆分成四个部分，每一个部分都会满足一定的性质，如小於等於pivot等等...，这样的性质可以做为循环不变量使用。

整个Quicksort的概念，以A = {6 10 13 5 8 3 2 11}作为举例

6 10 13 5 8 3 2 11, 选取6作为pivot
^  ^
i  j        ,j开始往後走，直到找到元素小於pivot, 找到时, 进行交换
------------------------------------------------------
6 10 13 5 8 3 2 11
  ^     ^
  i     j  ,i = i + 1
------------------------------------------------------
6 5 13 10 8 3 2 11
  ^     ^
  i     j  ,交换
------------------------------------------------------
6 5 3 10 8 13 2 11
    ^         ^
    i         j
------------------------------------------------------
6 5 3 2 8 13 10 11
      ^           ^
      i           j->
------------------------------------------------------
6 5 3 2 8 13 10 11
^     ^
pivot i     ,最後, pivot和i指到的元素进行交换，也就是将pivot移到中间
------------------------------------------------------
2 5 3 6 8 13 10 11
      ^
    pivot
我们会发现pivot左边都比他小，右边都比他大

整个程序大约会将阵列划分成4个部分，如下图

会划分成比pivot小的，比pivot大的，pivot本身，若r不等於阵列最後的index，则会有一个部分是和pivot无关的，这个例子中只有三个部分。

C++进行实作

#include <iostream>

using namespace std;
void quick_sort(int *, int, int);
int partition(int *, int, int);
int main(void)
{
    int A[10] = {2, 7, 3, 6, 1, 9, 0, 4, 7, 3};
    quick_sort(A, 0, 9);
    for (auto i : A)
    {
        cout << i << ' ';
    }
}

void quick_sort(int *a, int low, int high)
{
    if (low < high)
    {
        int q = partition(a, low, high);
        quick_sort(a, low, q - 1);
        quick_sort(a, q + 1, high);
    }
}

int partition(int *a, int low, int high)
{
    int pivot = a[high];
    int i = low - 1;
    for (int j = low; j <= high - 1; j++)
    {
        if (a[j] <= pivot)
        {
            i = i + 1;
            swap(a[i], a[j]);
        }
    }
    swap(a[i + 1], a[high]);
    return i + 1;
}

Quicksort效率

Quicksort的执行时间取决於在划分阵列时是否平衡，而平衡与否取决於划分的元素。如果划分时是平衡的，那Quicksort看起来会像是merge-sort一样，且有一样的效率。如果划分的不平衡，则会十分接近插入排序。

最坏情况

如果无法正常的划分阵列，则Quicksort的效率会十分的低落，如果我们选取的pivot都比其他的数来的大或是小，便无法把阵列平衡的划分了，而这样的情况会发生在整个阵列已经排序完毕，或是整个阵列是逆序排列的。也就是当两个子阵列分别一个出现n - 1个元素，另一个阵列出现0个元素时。
划分阵列的操作大概需要。由於对一个大小为0的阵列进行递回呼叫会直接回传，因此，因此整个时间复杂度可以表示成下面

，使用主方法後，得到结果为，而插入排序法最坏的情况也是，因此，在最坏的情况下，Quicksort的执行效率不比插入排序法来的好。但是对於已经排序好的阵列来说，Quicksort复杂度仍然是，此时插入排序法的时间复杂度为，效率比Quicksort来的好。

总共有n个，每一个执行时间为，因此n个时间复杂度为，整个为

最好情况

Quicksort的平均情况接近於其最好情况，而非其最差情况。假设我们在划分阵列的时候两边元素的大小为9:1的形式，我们试着将在个情况下，Quicksort的递回式写出


我们将递回树画出，会发现左子树和右子树的高度不同，每一层我们将其加总，第一层n需要，第二层，同样需要，直到深度达到以後，每一层所需要的时间就会小於等於，因为右子树已经停止展开了，因此该层的加总不会到。

我们将每一层所需要的时间进行加总，得到，加上所有叶子所需要的时间，得到，这个不等式的上界为，下界为，因此可以表示成，也可以表示成。(如果要求严谨必须使用代换法进行证明)

我们在来看到如果我们进行Quicksort，刚好遇到恰好将阵列划分成两个区块的情况，可以表示成，使用主定理得到结果为。

到这里证明完一件事情，即便阵列拆分的极度不平衡，他们的效率是一样好的，都是。

平均情况

对於Quicksort来说，他的行为取决维阵列中每一个元素的相对位置，而不是元素本身，因此，我们需要对输入各种情况的频率做出假设。

假设我们一开始是幸运的，刚好将阵列1:1划分，接着出现不幸运的情况，将阵列9:1划分，接着又出现幸运的情况，我们试着分析这样的情况。假设幸运的情况为，不幸运为

我们可以列出下面的式子，每一次幸运之後会接着不幸运，不幸运後会接着幸运

使用代换法求解:
解，将代换掉，先将带入，得到
，再将其代回，得到

(使用主定理)

这个情况下，总体来说，我们是幸运的

这张图表示先出现不幸运的划分，再出现幸运的划分，待解决的为和，也就是灰色矩形的部分

这张图表示一开始就出现幸运的划分，待解决的问题同样是两个灰色矩形的部分

这里有一个问题，我们的幸运只考虑阵列划分的方式，而没有考虑阵列中元素排序的方式，如果阵列中的元素是已经排序完成的或逆序的，时间复杂度为，为了确保我们是幸运的，这里有两个做法，第一个为随机排序阵列中的元素，另一种是随机选取基准点。

随机化Quicksort

在讨论随机化Quicksort的平均情况之前，会先假设输入的数据的所有种组合的机率都是相等的(实际上不会如此)，这麽做的好处，就是我们不用考虑输入阵列元素的顺序，不论输入什麽元素，届时都将是随机排序的，而因为Quicksort不会受到元素大小影响，因此元素的数值我们也不用在意了。不同於原本的Quicksort，在已经排序的情况下效率低落。也因此我们不需要对输入的阵列中元素的分布有任何假设，像是确定没有完成排序等等。没有任何一种输入是确定会发生最差的执行效率，会产生出最差执行效率的情况取决於随机数的产生。

现在最差的情况不由输入决定，而是取决於随机数产生器，数学上可以去计算出出现最差情况的边界，得到出现的可能性，为了方便分析，使用随机选取基准点(pivot)的方式进行随机化，不同於普通Quicksort每次选取作为基准点，我们使用的随机抽样为在中随机选取一个元素作为基准点。

达到这一件事情，实践的方式是将和中随机选取的元素进行交换。这模做可以确保基准点pivot = 是机率均等的从阵列个元素中随机选取的(这样随机选择也有可能选取到自己)。

RANDOMIZED-PARTITION(A, low ,high)
    i = RANDOM(p, r)
    exchange A[high] with A[i]
    return PARTITION(A, low, high)

RANDOMIZED-QUICKSORT(A, low, high)
if low < high
    q = RANDOMIZED-PARTITION(A, low, high)
    RANDOMIZED-QUICKSORT(A, low, high - 1)
    RANDOMIZED-QUICKSORT(A, q+1, high)

参考资料:Introduction to algorithms 3rd