sorting of bubbles with a variable number of inputs

The idea is to reserve the very first input for the length of the rest of the input. This way you can know when all the values have been taken. So in your example:

3 5 6 0

The actual input values would have to be

4 3 5 6 0

…where 4 tells us that 4 data values are following.

So this means that the program would start with something like:

     INP
     BRZ quit ; nothing to do
     STA size
     ; .... other code ....
quit HLT
size DAT 

Then the code would need to use this size to initialise a counter, and take the remaining inputs

        LDA size
        SUB one
loop    STA counter
        INP ; take the next input
        ; .... process this value ....
        LDA counter ; decrement the counter
        SUB one
        BRP loop ; while no underflow: repeat
        ; ... other processing on the collected input ...
quit    HLT
counter DAT

When you have several — possibly nested — loops, like is the case with bubble sort, you’ll have to manage multiple counters.

Applied to Bubble Sort

In this answer you’ll find an implementation of Bubble Sort where the input needs to be terminated by a 0. Here I provide you a variation of that solution where 0 no longer serves as an input terminator, but where the first input denotes the length of the array of values that follows in the input.

Note that this makes the code somewhat longer, and as a consequence the space that remains for storing the input array becomes smaller: here only 25 mailboxes remain available for the array. On a standard LMC it would never be possible to store 500 inputs, as there are only 100 mailboxes in total, and code occupies some of these mailboxes.

In the algorithm (after having loaded the input), the outer loop needs to iterate size-1 times, and the inner loop needs to iterate one time less each time the outer loop makes an iteration (this is the standard principle of Bubble Sort).

#input: 10 4 3 2 1 0 9 8 5 6 7 
         LDA setfirst
         STA setcurr1
         INP
         BRZ zero ; nothing to do
         SUB one
         STA size ; actually one less
input    STA counter1
         INP
setcurr1 STA array
         LDA setcurr1
         ADD one
         STA setcurr1
         LDA counter1
         SUB one
         BRP input
         LDA size
         BRA dec
sort     STA counter1
         LDA getfirst 
         STA getcurr1
         STA getcurr2
         LDA setfirst
         STA setcurr2
         LDA cmpfirst
         STA cmpcurr
         LDA counter1
loop     STA counter2
         LDA getcurr1 
         ADD one
         STA getnext1
         STA getnext2
         LDA setcurr2
         ADD one
         STA setnext
getnext1 LDA array
cmpcurr  SUB array
         BRP inc
getcurr1 LDA array
         STA temp
getnext2 LDA array
setcurr2 STA array
         LDA temp
setnext  STA array
inc      LDA getnext1 
         STA getcurr1
         LDA setnext
         STA setcurr2
         LDA cmpcurr
         ADD one
         STA cmpcurr
         LDA counter2
         SUB one
         BRP loop
         LDA counter1
dec      SUB one
         BRP sort
         LDA size
output   STA counter1
getcurr2 LDA array
         OUT
         LDA getcurr2
         ADD one
         STA getcurr2
         LDA counter1
         SUB one
         BRP output
zero     HLT
one      DAT 1 
getfirst LDA array
setfirst STA array
cmpfirst SUB array
size     DAT
counter1 DAT
counter2 DAT
temp     DAT
array    DAT

<script src="https://cdn.jsdelivr.net/gh/trincot/[email protected]/lmc.js"></script>

CLICK HERE to find out more related problems solutions.

Leave a Comment

Your email address will not be published.

Scroll to Top