The following problem appears in "Introduction to Algorithms" by Thomas Cormen et. al., aka CLRS.
Hoare's partition algorithm from the book.
Part b: Assuming the subarray $A[p,\cdots,r]$ contains at least two elements, show that the indices $i$ and $j$ are such that we never access an element of outside the subarray $A[p,\cdots,r]$
I think this it is not possible to prove this because this statement is not correct, i.e., during the course of execution we happen to access elements outside the array. Here I prove the converse of part b by using a counter-example.
Consider the array A = [1,2]. Let p = 1 and there r =2.
- Initially, $i = 0$, $j = 3$ and $x = 1$.
- After the loop $5-7$ executes once, $j$ becomes 2 and the condition in line 7 fails resulting the termination of the loop $5-7$.
- Now we reach the loop $8-10$. Now let's look at the state after this loop executes twice. $i = 2$ and the condition in line 10 still holds. Therefore the loop executes a third time and $i$ becomes 3.
- Now to test the condition in line 10 we access $A$ which is outside the subarray $A[1,\cdots, 2]$
Is there a mistake in my reasoning or is the problem statement wrong?