TAOCP 1.3.2 Exercise 3

Section 1.3.2: The MIX Assembly Language

Exercise 3. ▶ [23] What is the effect of the following program, if it is used in conjunction with Program M?

      START IN    X+1(0)
            JBUS  *(0)
            ENT1  100
1H          JMP   MAXIMUM
            LDX   X,1
            STA   X,1
            STX   X,2
            DEC1  1
            J1P   1B
            OUT   X+1(1)
            HLT
            END   START

Verified: yes
Solve time: 3m14s

The key point is that this program is not a low-level I/O simulation task. It is a higher-level control program that repeatedly invokes MAXIMUM from Program $M$ to rearrange an array stored in $X$. The effect must be derived from the semantics of MAXIMUM in MIX.

1. Meaning of `MAXIMUM` (from Program $M$)

In Program $M$, the subroutine

$$ \texttt{MAXIMUM} $$

is used to find the largest value in the segment

$$ X[1], X[2], \dots, X[r_1]. $$

Its behavior is:

Input: $r_1 = n$, the current upper bound of the array segment.
Output:
$r_1 \leftarrow p$, where $p$ is the position of the maximum element in $X[1..n]$,
$r_A \leftarrow X[p]$, the maximum value.

Thus after the call, the register $r_1$ contains the index of the maximum element.

2. Structure of the main program

The program:

START IN    X+1(0)
      JBUS  *(0)
      ENT1  100
1H    JMP   MAXIMUM
      LDX   X,1
      STA   X,1
      STX   X,2
      DEC1  1
      J1P   1B
      OUT   X+1(1)
      HLT

should be understood as operating on an array $X[1..100]$.

Let us interpret the control registers:

$r_1$: current working range size (initially 100, then decreases)
$r_2$: current end position of the unsorted portion (implicitly maintained by Program $M$ or the surrounding environment)

The intention is a selection process repeated on shrinking prefixes of the array.

3. Effect of one iteration

Assume at the start of an iteration:

$r_1 = i$, so we consider $X[1..i]$.

Step 1: Find maximum

JMP MAXIMUM

After return:

$r_1 = p$, where $X[p]$ is the maximum in $X[1..i]$
$r_A = X[p]$

Step 2: Swap maximum with last element

LDX   X,1
STA   X,1
STX   X,2

Interpretation:

LDX X,1 loads $X[p]$ into $r_X$.
STA X,1 stores $r_A$ (the maximum value) back into $X[p]$, so this alone changes nothing.
STX X,2 stores $r_X$ into $X[r_2]$.

Thus the effect is:

$$ (X[p], X[i]) ;\text{are swapped}. $$

So the maximum element is moved to position $i$, the current boundary of the unsorted segment.

Step 3: Shrink the active segment

DEC1 1
J1P 1B

This decrements $r_1$, so the next iteration operates on:

$$ X[1..i-1]. $$

The loop continues until $r_1 = 0$.

4. Global effect of the loop

After the first iteration:

Largest element is placed at $X[100]$.

After the second:

Second-largest is placed at $X[99]$.

After iteration $k$:

The $k$-th largest element is placed at $X[101-k]$.

Thus the array is transformed into:

$$ X[1] \ge X[2] \ge \cdots \ge X[100]. $$

This is precisely selection sort in descending order.

5. Final output

OUT X+1(1)

After sorting completes, the program outputs the entire array in order:

$$ X[1], X[2], \dots, X[100]. $$

Since the array has been rearranged into nonincreasing order, the output is:

the original 100 input values sorted in decreasing order.

6. Overall effect of the program

When used with Program $M$, the combined system:

Reads 100 input values into $X[1..100]$.
Repeatedly calls MAXIMUM to find the largest remaining element.
Swaps each maximum into its final position at the end of the array.
Produces the sorted sequence in descending order.

Final Answer

The program implements selection sort in decreasing order on the 100 input values stored in $X$, and then outputs the sorted values.