1

I have a code for quicksort in C++ that works perfectly for an array of non-unique elements. I'm sure that a lot of people here knows it, but, who does understand it? Let me explain myself better. This is the code:

void quicksort(int a[], int first, int last){
    int i,j;
    int pivot;

    if((last -first + 1) <= 1) return;

    pivot = a[(first+last) / 2];
    i = first;
    j = last;

    while(i <= j){
        while(a[i] < pivot) i++;
        while(a[j] > pivot) j--;

        if(i <= j){
            //SWAP
            int temp = a[i];
            a[i] = a[j];
            a[j] = temp;

            i++;
            j--;
        }
    }

    quicksort(a, first, j);
    quicksort(a,i, last);
}

So, i understand everything but the if on the swap. Can anyone tell me, mathematically, what is the exact case or set of cases where i > j after the two inner whiles? I know specific cases for it, but what is the mathematical (or exact) property of them for happening?

Sorry for the crappy english, and thanks.

PD: Ignore in this case optimizations, or choosing the pivot and all that stuff, please.

4

2 回答 2

1

如果在开始时 a[i] > pivot （所以 i 不会改变）并且 a[j] > pivot 对于所有 j 直到 a[j] = pivot ，循环的下一次迭代将导致 j 的情况< 一世。

为了显示...

取以下数组：

int a[] = [10, 7, 2, 6, 3];

在第一次调用快速排序时，first 为 0，last 为 4（数组中的最后一个索引），pivot 将为 a[2] = 2。在第一次迭代中，如果 while 循环，a[0] > 2，所以我没有改变。a[4] > 2, j--, a[3] > 2, j--, a[2] = 2，现在我们点击 if 语句。0 <= 2，所以我们交换 a[0] 和 a[2] 并执行 i++ 和 j--。

现在数组看起来像这样：

[2, 7, 10, 6, 3]

i = 1 且 j = 1。a[i] > 2，所以 i 不变。a[j] > 2，所以 j--，j 现在是 0。a[j] 不大于 2（因为它是 2），j 保持在 0。现在，我们有 i = 1 和 j = 0 , 或 i > j。

如果您注意到，2 处于“排序”位置，不再需要移动。此外，枢轴是数组中的最小元素。希望能帮助你弄清楚。

于 2013-10-09T19:11:44.990 回答
0

i并j从数组的任一端开始，直到找到大于枢轴 ( a[i]) 且小于枢轴 ( a[j]) 的值。当找到两个这样的值时，它们是交换位置，因此您最终会得到一个数组，在循环之后i到结尾大于枢轴，而开始到j小于枢轴。比我们递归这两个子数组。

i>j当列表完成除以枢轴值时。i并j覆盖了数组中的每个值，以确保它位于枢轴的正确一侧。这可能发生在数组的中间，或者根据枢轴值在列表中的位置仅交换一个值之后。枢轴可以是最大值或最小值，也可以位于值列表的中间。

于 2013-10-09T19:15:35.903 回答