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

This version of the code will start by asking the user to enter 10 different numerical values that the code will then sort.

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

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

For each iteration of the Bubble sort algorithm we set a “sorted” flag to true.

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

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.

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.

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.

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.

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

Tagged with: