Problem 7.1: Hoare's partition algorithm goes out of array's bound when input is already sorted

[vkWeb]

In problem 7.1 part b, we are asked to prove the correctness of hoare's partition algorithm by arguing that the algo doesn't access elements outside the array.

Suppose the input array A is already sorted like 2 9 10 25 then the algo keeps on incrementing i and we eventually access array[4] (out of bounds) which violates its correctness.

Here's an example C code of Hoare's partition designed to prove my argument. If I'm wrong then please correct me and guide me to the right direction :)

int arr[] = {2, 9, 10, 25}; int len = sizeof arr / sizeof arr[0];
int x = arr[0];
int i = -1, j = len;

while (1) {
    do {
        --j;
    } while (arr[j] <= x);

    do {
        ++i;
    } while (arr[i] >= x);

    if (i < j) {
        swap(&arr[i], &arr[j]);
    } else {
        return j;
    }
}

[vkWeb]

@aakashpothepalli what do you think about my above argument? Is my view on this correct or am I mistaken?

Please guide me my friend :)

[aakashpothepalli]

Thanks for tagging me @vkWeb But I'm afraid that I'm not familiar with the algorithm. I'll study about it and get back to you :)

[Xeuva]

Your loop is wrong. The loop should be do {++i} while(arr[i]<x); the loop in original algorithm uses repeat A until B, which is the same as do A while not B.

[vkWeb]

@Xeuva making that change still let us loop out of bounds. Try running the algorithm with sorted array as an input.

My code reflects this algorithm as presented in CLRS 2nd & 3rd edition, as you can see my loop is correct, the algorithm needs to handle the out of bounds:

HOARE-PARTITION(A, p, r)
    x = A[p]
    i = p - 1
    j = r + 1
    while true
        repeat
            j = j - 1
        until A[j] ≤ x
        repeat
            i = i + 1
        until A[i] ≥ x
        if i < j
            exchange A[i] with A[j]
        else return j

[vkWeb]

@aakashpothepalli no problem mate! I'll wait for your reply.

[Xeuva]

Take input array [2,9,10,25] as an example. In Hoare partition, initialization: p=0, r=3, x=2, i=-1, j=4 during while loop: line 5-7 decreases j UNTIL A[j] <=x. Because array is sorted, only the first element satisfies A[j] <=x, finally j = 0. line 8-10 increases i UNTIL A[i] >=x. Because A[0]=2, x=2, so it satisfies A[i]>=x. No need to increase i, so the while loop exits. When this two while loop exits, i = j = 0. In the end return j, whose value is 0.

The error in your codes is the condition in do...while loop.

[vkWeb]

@Xeuva :thinking: isn't "repeat until" same as do while loop...? we execute the code in repeat block until the while condition is true and we exit the loop when the condition becomes false?

If you agree with my above understanding then,

input: 2, 3, 5, 10 (already sorted)
       i        j

pivot is 2.

j stops at 10 as 10 is not smaller than equal to 2.

i increases as 2 >= 2 is true then again 3 >= 2 true, 5 >= 2 true, we keep on incrementing i and eventually run out of bounds.

What do you think about this?

The correction is that the while condition should not include equals in less than and greater than. The correct algo IMO should be: (the algo given in the book is designed to sort in descending order as I understand)

HOARE-PARTITION(A, p, r)
    x = A[p]
    i = p - 1
    j = r + 1
    while true
        repeat
            j = j - 1
        until A[j] < x
        repeat
            i = i + 1
        until A[i] > x
        if i < j
            exchange A[i] with A[j]
        else return j

[Xeuva]

From Do_while_loop wiki, it says that

Some languages may use a different naming convention for this type of loop. For example, the Pascal language has a "repeat until" loop, which continues to run until the control expression is true (and then terminates) — whereas a "while" loop runs while the control expression is true (and terminates once the expression becomes false).

And in "Pascal" section, it says that

Pascal does not have a do/while; instead, it has a repeat/until. As mentioned in the introduction, one can consider a repeat/until to be equivalent to a 'do code while not expression' construct.

In "repeat until" loop, the loop terminates when condition is true. In "while" or "do while" loop, the loop terminates when conditions is false.

[vkWeb]

@Xeuva Ohhh - yes you are right. If that's the case then the algorithm is perfect! Thanks @Xeuva for the help buddy :smile: