Bubble Sort Algorithm in LMC

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
       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   

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
       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

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
       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