Questions about Hoare's partition scheme

I struggle to implement Hoare's partition scheme as shown in the original article here (Algorithm 63):

ALGORITHM 63
PARTITION
C. A. R. Hoare
Elliott Brothers Ltd., Borehamwood, Hertfordshire, Eng.
procedure  partition (A,M,N,I,J);  value M,N; 
            array A;  integer M,N,I,J;
comment I and J are output variables, and A is the array (with subscript bounds M:N) which is operated upon by this procedure. Partition takes the value X of a random element of the array A, and rearranges the values of the elements of the array in such a way that there exist integers I and J with the following properties:
                M ≤ J < I ≤ N provided M < N 
                A[R] ≤ X for M ≤ R ≤ J 
                A[R] = X for J < R < I 
                A[R] ≥ X for I ≤ R ≤ N 
The procedure uses an integer procedure random (M,N) which chooses equiprobably a random integer F between M and N, and also a procedure exchange, which exchanges the values of its two parameters;
begin   real X;  integer F; 
        F := random (M,N);  X := A[F]; 
        I := M;  J := N; 
up:     for I := I step 1 until N do 
                   if X < A [I] then go to down; 
        I := N; 
down:   for J := J step -1 until M do 
                   if A[J]<X then go to change; 
        J := M; 
change: if I < J then begin exchange (A[I], A[J]); 
                            I := I + 1; J := J - 1; 
                            go to up 
                      end 
else    if I < F then begin exchange (A[I], A[F]); 
                            I := I + 1
                      end 
else    if F < J then begin exchange (A[F], A[J]); 
                            J := J - 1 
                      end; 
end     partition

I don't understand some variable's initializations, i.e. I:=N and J:=M.

For the up part, there is:

    for I := I step 1 until N do
                if X < A[I] then go to down;
    I := N

When is this supposed to occur? Since if it is outside of the loop it seems to always be skipped.

Later in the algorithm, there is:

    if I < F then begin exchange (A[I], A[F]);
                        I := I + 1
                  end

As exchange (A[I], A[F]) isn't on a new line, does it mean that A[I] and A[F] must be exchanged or that I := I + 1 is supposed to exchange the values?

What is this algorithm supposed to return?

Solution

I don't understand some variable's initializations, i.e. I:=N and J:=M.

These are executed when the preceding loop finished all iterations without premature exit via the go to statement. I don't know whether all Algol60 compilers at the time would be consistent in which value the loop variable would have after finishing the loop, and this assignment just ensures that it is the "until" value of the loop range.

Since if it is outside of the loop it seems to always be skipped.

They are only skipped if the go to was executed, but there can be cases where the loop finishes without this happening.

As exchange (A[I], A[F]) isn't on a new line, does it mean that A[I] and A[F] must be exchanged or that I := I + 1 is supposed to exchange the values?

The layout of the code is confusing you. You can interpret it as follows:

if I < F then
begin
    exchange (A[I], A[F]); 
    I := I + 1
end

What is this algorithm supposed to return?

It is a procedure and so it doesn't have a return value. But the parameters I and J are called by reference, so the caller will get information back via those variables. Their significance is explained in the article:

                M ≤ J < I ≤ N provided M < N 
                A[R] ≤ X for M ≤ R ≤ J 
                A[R] = X for J < R < I 
                A[R] ≥ X for I ≤ R ≤ N

Implementation

As the presented code relies on call-by-reference, we could map it to C++. Here is an implementation, where I have stayed as close as possible to the original code (indentation, use of goto and labels, ...), completed with quickSort and driver code:

#include <iostream>

int random(int low, int high) {
    return std::rand() % (high - low + 1) + low; 
}

void exchange(float &a, float &b) {
    float c = a;
    a = b;
    b = c;
}

void partition(float A[], int M, int N, int &I, int &J) {
begin:  float X; int F;
        F = random(M,N); X = A[F]; 
        I = M; J = N;
    
up:     for (I = I; I <= N; I += 1)
            if (X < A[I]) goto down;
        I = N;
    
down:   for (J = J; J >= M; J -= 1)
            if (A[J] < X) goto change; 
        J = M;
    
change: if (I < J) {  exchange(A[I], A[J]); 
                      I = I + 1; J = J - 1; 
                      goto up;
                   } 
   else if (I < F) {  exchange (A[I], A[F]); 
                      I = I + 1;
                   } 
   else if (F < J) {  exchange (A[F], A[J]); 
                      J = J - 1;
                   } 
}

void quickSort(float A[], int M, int N) {
    int I, J;
    if (M < N) {
        partition(A, M, N, I, J);
        quickSort(A, M, J);
        quickSort(A, I, N);
    }    
}

void printArr(float A[], int size) {
    for (int i = 0; i < size; i++) {
        std::cout << A[i] << " ";
    }
    std::cout << "\n";
}

int main()
{
    int size = 14;
    float A[] = {1, 5, 1, 9, 3, 4, 2, 8, 9, 4, 7, 7, 6, 8};
    std::srand(time(NULL));

    printArr(A, size); // Before sorting
    quickSort(A, 0, size - 1);
    printArr(A, size); // After sorting

    return 0;
}