# Quick sort, Hoare's partition algorithm. Is there a mistake in CLRS?

The following problem appears in "Introduction to Algorithms" by Thomas Cormen et. al., aka CLRS.

Problem 7-1.b

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[3]$$ which is outside the subarray $$A[1,\cdots, 2]$$

Is there a mistake in my reasoning or is the problem statement wrong?

• After the loop $5-7$, $j$ becomes $1$ since $A[2] > x$. May 6 '21 at 17:07
• After loop $8−10$, $i$ becomes $1$ since $A[1] = x$. May 6 '21 at 17:09
• Since $i = j = 1$, the algorithm terminates and return $1$. May 6 '21 at 17:10

The problem statement is correct.

I think you getting confused about: repeat $$j \gets j-1$$ until $$A[j] \leq x$$. It means that if $$A[j]>x$$ then do $$j \gets j-1$$.

Similarly, loop $$8-10$$ means that if $$A[i] then do $$i \gets i+1$$.

Therefore, the algorithm executes in the following way on $$A = [1,2]$$:

1. After the loop $$5-7$$, $$j$$ becomes $$1$$ since $$A[2] > x$$.

2. After loop $$8−10$$, $$i$$ becomes $$1$$ since $$A[1] = x$$.

3. Since $$i = j = 1$$, the algorithm terminates and returns $$1$$.

• Thanks a lot! I understand now. May 7 '21 at 7:53