Algorithm is proved

The proof of the algorithm uses the circular invariant method in introduction to algorithms

Quick row template (delimited by J)

Quicksort belongs to the divide-and-conquer algorithm, which has three steps:

  1. Subdivision problem
  2. Do subproblems recursively
  3. Subproblem combination
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); // Step 3: subproblem merge. There is no need for quicksort, but the heart of merge sort is in this step.Copy the code

For the problem

After the while loop ends,q[L..j] <= x,q[j+1..r] >= x

Note :q[l.. J] <= x meaning q[l],q[L +1]… Q [j-1], all elements of q[j] are <= x

prove

Cyclic invariant: q[l.. I] <= x q[J.. R] >= x

  1. Initialize the

Before the cycle starts I is l minus 1, j is r plus 1

Then q[L.. I] and Q [J..r] are empty, and the cyclic invariant is obviously valid

  1. keep

Assume that the cycle invariant holds before the start of a cycle, i.e. Q [L.. I] <= x, q[J.. R] >= x

Execution loop body

do i++; while(q[i] < x); Q [l.. I -1] <= x, q[I] >= x do j--; while(q[j] > x); [j + 1 will make the q.. r] > = x, q [j] < = x if (I < j) swap (q [I], q [j]); Q [L.. I] <= x, q[J.. R] >= xCopy the code

So, after I and j are updated, the loop invariant still holds until the next loop starts

Note: since we use the do-while loop, I and j must!! Since the increase!!!!!! , so that the loop will continue, but if you use a while loop (the initialization of I and j makes the corresponding changes), the loop will be stuck if I and j do not increment in special cases

Such as:

while(q[i] < x) i++; while(q[j] > x) j--; When q[I] and q[j] are both x, neither I nor j is updated, causing the while to fall into an infinite loopCopy the code

  1. Termination of

    At the end of the loop, I >= j

    Under normal circumstances, with cyclic invariants, we should think it’s obvious

    Because I >= j, q[L.. I] <= x, q[J.. R] >= x

    Q [l..j] <= x, q[j+1..r] >= x is obvious

    However, the last loop is a bit special because the if statement for the last loop is definitely not executed

    The if statement must not be executed because the last loop must be I >= j, otherwise the while loop would not be broken

    Correct analysis:

    Because the last round of the if statement must not be executed

    So, the only guarantee I > = j and q [l.. I – 1] [I] > < = x, q = x and q [j + 1 r] > = x, q [j] < = x

    By the q [l.. I – 1) < = x, I > = j (I – 1 > = j – 1) and q [j] < = x can get q [l.. j] < = x

    And because q [j + 1.. r] > = x so, q [l.. j] < = x, q [j + 1 r] > = x, issue certificate

    Conclusion: Only at the end of the last cycle, the cycle invariant is not true, the rest of the cycle is true but the final problem is solved

    Note: Remember to check at the end of the loop for out-of-bounds/infinite recursion of the array

    Therefore, it is still necessary to prove that the final value range of j is [L… R-1](that is, there is no infinite recursion in which N is divided into 0 and N), and the analysis process is analyzing 5

Boundary case analysis

Analysis of the

Quicksort is a divide-and-conquer algorithm, and the worst thing you can do is divide n into 0 and n, or n into n and 0, which creates an infinite partition

  1. In order tojIs divided into,xCan’t chooseq[r](if theiIs divided, thenxCan’t chooseq[l])

Suppose x = q[r]

Key sentences quick_sort(q, L, j), quick_sort(q, j + 1, r);

Since the minimum value of j is L, q[j+1..r] does not cause infinite partition

But q[L..j](quick_sort(q, L, j)) may result in an infinite partition because j may be r

For example, if x is selected as q[r], q[L..r-1] < x,

So at the end of this cycle I = r, j = r, it’s obviously going to be an infinite partition

  1. do i++; While (q[I] < x) and do j–; While (q[j] > x) cannot use q[I] <= x and q[j] >= x

    Assume that q[L..r] is completely equal

    Do i++; while(q[i] <= x); After that, I will increment to r+1

    Q [I] <= x = q[I] <= x

    And if the subsequent condition q[I] <= x (where I > r) is also unfortunately true,

    The loop will continue forever, causing the Memory Limit to Exceeded.

  2. If (I < j) swap(q[I], q[j]) can use I <= j

    If (I <= j) swap(q[I], q[j]);

    Because when I is equal to j, if YOU swap q[I],q[j] doesn’t matter, because you’re immediately out of the loop

  3. Quick_sort (q, l, j-1), quick_sort(q, j, r)

    Can’t

    According to the previous proof, the last round of the cycle leads to these conclusions

    J < = I and q [l.. I – 1] [I] > < = x, q = x and q [j + 1 r] > = x, q [j] < = x

    Therefore, q[L.. J-1] <= x is clearly true,

    Q [j] in quick_sort(q, j, r) is q[j]

    Also, note that quick_sort(q, L, J-1), quick_sort(q, j, r) may cause wireless partitioning

    If x is set to q[l], the partition will be infinite, and the error is (MLE),

    If you manually change to x = q[r], you can avoid infinite partitioning

    But the above problem of q[j] <= x still cannot be solved, which will cause WA (Wrong Answer)

  4. The value range of j is [L..r-1]

Proof:

Assuming that the final value of j is r, it means that there is only one cycle (for two rounds j will subtract itself at least twice).

Statement q[r] <= x (because we want to break out of the do-while loop)

I >= r (end condition of while loop), I is r or r + 1(must not be true)

Q [r] >= x and q[L..r-1] < x,

It is concluded that q[r] = x and Q [L..r-1] < x, but this contradicts x = q[L + r >> 1]

Reduction shows that j is less than r

Assuming that j may be less than L implies that q[L..r] > x, paradoxically

Reduction shows that j is greater than l

So the value range of j is [L..r-1], which does not cause infinite partition and array transgression

  1. whileCan the end of the loop be changed toi <= j

By the way, I’m going to be the template for partition

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 >> 1]; While (I < j) {do I ++; q[l] 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, i - 1), quick_sort(q, i, r); // Q [l.. I],q[I +1..r] is the same as j in analysis 4.Copy the code