The aim of this challenge is to implement a Bubble sort algorithm on a list of 10 values using LMC.

We will be using our online LMC simulator to test our code

online LMC simulator:

LMC SimulatorOpen in New Window

**from line 70 to 79.**

init LDA v0 STA 90 LDA v1 STA 91 LDA v2 STA 92 LDA v3 STA 93 LDA v4 STA 94 LDA v5 STA 95 LDA v6 STA 96 LDA v7 STA 97 LDA v8 STA 98 LDA v9 STA 99 loop LDA true STA sorted LDA first STA pos ADD one STA next step LDA @pos SUB @next BRZ pass BRP swap pass LDA pos ADD one STA pos LDA next ADD one STA next LDA pos SUB last BRZ repeat BRA step swap LDA @next STA temp LDA @pos STA @next LDA temp STA @pos LDA false STA sorted BRA pass repeat LDA sorted SUB true BRZ exit BRA loop exit OUT HLT pos DAT next DAT temp DAT sorted DAT 0 true DAT 1 false DAT 0 one DAT 1 first DAT 90 last DAT 99 v0 DAT 32 v1 DAT 7 v2 DAT 19 v3 DAT 75 v4 DAT 21 v5 DAT 14 v6 DAT 95 v7 DAT 35 v8 DAT 61 v9 DAT 50

init INP STA 90 INP STA 91 INP STA 92 INP STA 93 INP STA 94 INP STA 95 INP STA 96 INP STA 97 INP STA 98 INP STA 99 loop LDA true STA sorted LDA first STA pos ADD one STA next step LDA @pos SUB @next BRZ pass BRP swap pass LDA pos ADD one STA pos LDA next ADD one STA next LDA pos SUB last BRZ repeat BRA step swap LDA @next STA temp LDA @pos STA @next LDA temp STA @pos LDA false STA sorted BRA pass repeat LDA sorted SUB true BRZ exit BRA loop exit OUT HLT pos DAT next DAT temp DAT sorted DAT 0 true DAT 1 false DAT 0 one DAT 1 first DAT 90 last DAT 99

#### Executing the Code

We will be using our online LMC simulator to test our code

online LMC simulator:

LMC SimulatorOpen in New Window

Before testing this code in the online LMC simulator, we recommend increasing the clock speed:

We also recommend turning off the log file:

This will significantly reduce the execution time. With the data given, it will still take 831 FDE cycles to sort all 10 numbers:

#### Code Review

Let’s review how this code was constructed:

This is done at the very start of the code in the *init* block:

init LDA v0 STA 90 LDA v1 STA 91 LDA v2 STA 92 LDA v3 STA 93 LDA v4 STA 94 LDA v5 STA 95 LDA v6 STA 96 LDA v7 STA 97 LDA v8 STA 98 LDA v9 STA 99

This code is using the 10 labels v1 to v9 declared at the end of the code from line 70:

v0 DAT 32 v1 DAT 7 v2 DAT 19 v3 DAT 75 v4 DAT 21 v5 DAT 14 v6 DAT 95 v7 DAT 35 v8 DAT 61 v9 DAT 50

loop LDA true STA sorted

This flag will be overwritten if when scanning through the list a swap is made. If after checking all values of the list, the “sorted” flag is still equal to true, in this case we can deduct that the list if fully sorted and hence stop iterating.

We then reset the two pointers “pos” and “next” to first two memory locations of the list (memory location 90 (first) and 91 (first ADD one).

LDA first STA pos ADD one STA next

We can now compare the two adjacent values at position “pos” and “next” (=pos+1). Note the use of **indirect addressing** using the @ symbol to access the values stored at the address stored at position “pos” and “next”. To compare both values we perform a SUB (subtract) operation.

If the current value (@pos) is greater then the next value (@next) then the subtraction will be positive. If both adjacent values are equal then the subtraction will be null and there is no need to swap both values (BRZ pass). If not, if the subtraction is a positive number (>0) then we will swap both values: BRP swap. If not we will move on the next section of code to pass without swapping.

step LDA @pos SUB @next BRZ pass BRP swap

To pass, we increment both pointers “pos” and “next” by 1 so that we can then repeat the process with the next two values (by branching to the “step” block of code). However, we also need to check if we have reached the end of the list (if the “next” pointer is pointing to the last value in the list. In this case we would need to check if we need to start a new iteration of the Bubble sort algorithm from the very start of the list, or whether we can stop here (if the list is already fully sorted). This check will be performed in the “repeat” block of code.

pass LDA pos ADD one STA pos LDA next ADD one STA next LDA pos SUB last BRZ repeat BRA step

Below is the code used to swap both adjacent values (at position “@pos” and “@next”). This also sets the “sorted” flag to false, to indicate that the list may not be fully sorted yet and that a new iteration of the Bubble Sort will be needed.

swap LDA @next STA temp LDA @pos STA @next LDA temp STA @pos LDA false STA sorted BRA pass

The “repeat” block of code is used to decide whether the list is fully sorted or whether a new full iteration of the list is needed to continue the sorting process. This is done by checking that the flag “sorted” is true or false. If it is true, then the list is sorted and we can stop the Bubble Sort algorithm by branching to the “exit” block of code. Otherwise we are going back to the star of the process by branching to the “loop” block of code.

repeat LDA sorted SUB true BRZ exit BRA loop

Finally, the “exit” block of code is used to inform the user that the list is now fully sorted. This is done by outputting the value 0 and stopping the process (HLT instruction).

exit OUT HLT