# Bubble Sort Algorithm in LMC

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 code using hardcoded valuesLMC code using input values
To simplify the testing process (and nto having to input 10 values each time we want to run/test the code, we have created a version of our Bubble sort algorithm where the 10 values are hardcoded in the code itself. You can change these values (v1 to v10) in the code 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
STA next
step   LDA @pos
SUB @next
BRZ pass
BRP swap

pass   LDA pos
STA pos
LDA next
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   ```
This version of the code will start by asking the user to enter 10 different numerical values that the code will then sort.

```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
STA next
step   LDA @pos
SUB @next
BRZ pass
BRP swap

pass   LDA pos
STA pos
LDA next
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:

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:

InitialisationBubble Sort
When running this code using the LMC simulator, you will notice that the first action performed by this code is to store the 10 given values in the RAM using locations 90 to 99:

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   ```
For each iteration of the Bubble sort algorithm we set a “sorted” flag to true.

```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
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
STA pos
LDA next
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```

Did you like this challenge?

Click on a star to rate it!

Average rating 4.5 / 5. Vote count: 13

No votes so far! Be the first to rate this post.

As you found this challenge interesting...