0
$\begingroup$

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.

enter image description here

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?

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

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]<x$ 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$.

$\endgroup$
1
  • $\begingroup$ Thanks a lot! I understand now. $\endgroup$ May 7 at 7:53

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.