This article was written when I was learning algorithms. Boy, the first question got me stuck for a long time. But the good news is that I didn’t get by and spent the evening and morning going through everything and thinking through the iteration process. After that, I felt that I had entered the door and had a feeling. The following other topics did not card me for so long.
Exceeded by very simple quick-sort code running status: Memory Limit Exceeded half a day.
Finally pondering half a day to cross the boundary this matter. To sum up: avoid func(l, r) {… func(l, r) … } (the boundary value passed to the next level does not shrink when recursing), because this is an infinite loop. How to avoid it? For example, func(l, r) {func(l, j), func(j + 1, r)}, j at least satisfies j > r (j leaves from r, in case func(l, j) is func(l, r)).
#include <iostream>
using namespace std; const int N = 1e6 + 10; int n; int q[N];
void quick_sort(int q[], int l, int r)
{
if (l >= r) return;
int i = l - 1, j = r + 1, x = q[l + r >> 1];
while (i < j)
{
do i ++; while (q[i] < x);
do j --; while (q[j] > x);
if (i < j) swap(q[i], q[j]);
}
quick_sort(q, l, j), quick_sort(q, j + 1, r);
}
int main() { scanf("%d", &n); for (int i = 0; i < n; i ++) scanf("%d", &q[i]); quick_sort(q, 0, n-1); for (int i = 0; i < n; i ++) printf("%d ", q[i]); return 0; }My hand is out of control, I have to write it as:
quick_sort(q, l, i - 1), quick_sort(q, i, r);Oh, boy. Error. I didn’t see it for a long time, but then I realized that if you wanted to use I, it would be x = q[l + r + 1 >> 1]; .
Can’t I go down like this?
x = q[l+r >> 1]; . quick_sort(q, l, j - 1), quick_sort(q, j, r); // Or is this not a good idea? x = q[l+r >> 1]; . quick_sort(q, l, i - 1), quick_sort(q, i, r); // Or is this not a good idea? x = q[l+r >> 1]; . quick_sort(q, l, i), quick_sort(q, i + 1, r); // Or is this not a good idea? x = q[l+r+1 >> 1]; . quick_sort(q, l, j), quick_sort(q, j + 1, r); // Or is this not a good idea? x = q[l+r+1 >> 1]; . quick_sort(q, l, j - 1), quick_sort(q, j, r); // Or is this not a good idea? x = q[l+r+1 >> 1]; . quick_sort(q, l, i), quick_sort(q, i + 1, r);None of the above can do. Let me give you an example.
If we enter an array of length 2, then the first level of the loop: l = 0, r = 1 (i.e., quick_sort(0, 1)). If we enter the second level of the loop and quick_sort(0, 1) also occurs, then we are in an infinite loop.
In the following table, “I, j passed to function” refers to a call to quick_sort(q, l,? i/j), quick_sort(q, ? The values of I and j in I /j, r.
In the following table, the last column marked with X indicates that the program will be stuck in an infinite loop.
Int mid = l+r >> 1; :
| The test case | q[mid] |
Passed to a functioni, j |
Incoming parameters |
|---|---|---|---|
0 1 |
0 | 0, 0 |
j-1 j= >(0, -1), (0, 1)x |
0 1 |
0 | 0, 0 |
i-1 i= >(0, -1), (0, 1)x |
0 1 |
0 | 0, 0 |
j j+1= >(0, 0), (1, 1)Square root |
1 0 |
1 | 1, 0 |
i i+1= >(0, 1)x, (2, 1) |
1 0 |
1 | 1, 0 |
j j+1= >(0, 0), (1, 1)Square root |
Int mid = l+r >> 1; int mid = l+r >> 1; , only j, j+1 of the four combinations withstood the double test of 0, 1 and 1, 0.
Int mid = l+r+1 >> 1; :
| The test case | q[mid] |
Passed to a functioni, j |
Incoming parameters |
|---|---|---|---|
1 0 |
0 | 1, 0 |
j-1 j= >(0, -1), (0, 1)x |
1 0 |
0 | 1, 0 |
i i+1= >(0, 1)x, (2, 1) |
1 0 |
0 | 1, 0 |
i-1 i= >(0, 0), (1, 1)Square root |
0 1 |
1 | 1, 1 |
j j+1= >(0, 1)x, (2, 1) |
0 1 |
1 | 1, 1 |
i-1 i= >(0, 0), (1, 1)Square root |
Int mid = l+r+1 >> 1; Of the four combinations, only I -1 I withstood the double test of 0, 1 and 1, 0.
Why is that?
- Here is the relevant proof: ACWING 785. The proof of quicksort algorithm and boundary analysis
- If you don’t have the patience to see the more rigorous proofs above, you can see what I wrote at the end of the article
My stupid way of thinking about it is:
int mid = l+r >> 1;: can be provedjThe range of theta is theta[l, r-1], so for boundary combinationsj j+1有Quick_sort (q, l, j < r), Quick_sort (q, j+1 > l, r)There never will bequick_sort(q, l, r)Appear.int mid = l+r+1 >> 1;: can be provediThe range of theta is theta[l+1, r], so for boundary combinationsi-1 i有Quick_sort (q, l, I -1 less than r), Quick_sort (q, I greater than l, r)There never will bequick_sort(q, l, r)Appear.
OK, so this is reciting:
- Fast row,
int mid = l+r >> 1;(midRound down), yesj j+1Because thejThe range of values is[l r-1] - Personally, I don’t like reciting, but I still know the principle, so I think I can quickly derive it. The derivation is as follows.
Prove it in a clear but clumsy waymidRounding downjBelong to[l, r-1].
J belonging to [l, r-1] == when rounding down is equivalent to == at least twice j– is performed when rounding down
The following three special cases are discussed (the general case is not discussed), it can be seen that there are at least two j– executed in all three cases
Case 1: j at r is no longer q[j] > x, but I at l still satisfies q[I] < x
q[mid] x 9 8 begin i j step1 i j do i++; while(q[i] < x); step2 i j do j--; while(q[j] > x); step3 8 9 step4 i j swap(q[i], q[j]); step5 ij do i++; while(q[i] < x); step6 j i do j--; while(q[j] > x); While (I < j) {}J at r is no longer q[j] > x, but I at l is still q[I] < x; So for l < r, we have to do another round, because we’re doing while instead of while do, so no matter what the I or j condition is, we have to do at least one more time I ++; j–; .
Case 2: j also satisfies q[j] > x at r, but I is no longer q[I] < x at l
q[mid] x 8 9 begin i j step1 i j do i++; while(q[i] < x); step2 ij do j--; while(q[j] > x); While (I < j) {}J also satisfies q[j] > x at r, so it must continue executing j–, j must be less than r.
Case 3: j is no longer q[j] > x at r, and I is no longer q[I] < x at l
q[mid] x 8 8 begin i j step1 i j do i++; while(q[i] < x); step2 i j do j--; while(q[j] > x); step3 8 8 step4 i j swap(q[i], q[j]); step5 ij do i++; while(q[i] < x); step6 j i do j--; while(q[j] > x); While (I < j) {}J [j] > x is no longer q[j] > x, and I is no longer q[I] < x; I have I < j, so I don’t break out of the loop, swap; For l < r, we have to do another round, because we’re doing while instead of while do, so no matter what the I or j condition is, we have to do it at least once more, I ++; j–; .
-Sheldon: Anyway, if you can do it or not, I’ll move it for you, and then you can judge.
For the dichotomy, the core idea is also to avoid the occurrence of func(l, r) {func(l, r); } mid = l + r >> 1; So it must be r = mid; Well, because mid is rounded down, if l is less than r mid will never touch r.
I am a small pat, remember to pay attention to a look!