quicksort invariant 3 conditions with loop invariant

Question

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:

Here is the algorithm I'm referencing:

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

Answer 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

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.

Answer 2

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 $