1
$\begingroup$

in studying Quicksort using the book "Introduction to Algorithms" by Cormen, Leiserson, Rivest and Stein, they describe in order to show correctness, an invariant must hold for the 3 stages of the loop, the initialization, the maintenance and termination of the loop.

Based on the following algorithm, I don't understand properties 1 and 2 below: enter image description here

Here is the algorithm I'm referencing:

enter image description here enter image description here

Might someone help me understand conditions

1) if $p \leq k \leq i$ then $A[k] \leq x$

In the algorithm when for example, $p$ is $1$, won't $i$ be $0$.... How would this hold, since before the for loop we have i = p-1

2) if $i + 1 \leq k \leq j - 1 $ then $A[k] > x$

In the algorithm for example, when we first enter the for loop, and j = 1, then $i$ would be 0.... I don't see how this works.

Thanks

$\endgroup$
1
$\begingroup$

If $p \leq k \leq i$ then $A[k] \leq x.$ In the algorithm when for example, $p$ is $1$, won't $i$ be $0$.... How would this hold, since before the for loop we have i = p-1

Although, as you have observed, $i$ is always smaller than $p$ at the start of the loop, it might become bigger because the statement "$i=i+1$" in the loop could be executed. Once $i$ has been increased, for at least $k=p$, we have $p\le k\le i$.

Note that when $p\le i$ does not hold, i.e., when there is no $k$ such that $p\le k\le i$, the condition "if $p \leq k \leq i$ then $A[k] \leq x$" holds automatically. (Recall that the proposition "if false, then anything can happen" is always true.) To falsify that condition, we have to find an instance of $(p,k,i)$ such that $p \leq k \leq i$ but $A[k]\gt x$.

You should be able to figure out the case of the second loop invariant now.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks @John L. this is clearer now! $\endgroup$ – Katie Melosto May 11 at 15:44
0
$\begingroup$

I'm not in the mood of tracing a code rightnow, but understand that u start with A[r] =X and ends with A[i] =X

(the pivot, which seems to be chosen as the last element $r$ in the given code, reaches its correct position with the rest of the list get paritioned)

-At a first glance maybe the code has some errors, there is no need for the exchange in the then brackets, and the other exchange should be bet A[r] & A[j] inside the $ else $

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.