little-man-computer

Bubble sort 4 numbers

I'm trying to code a bubble sort using the LMC, and well, it's not going too great.

First of all it just loops for all eternity, and I cannot figure out the cause, maybe a pair of fresh eyes would help?

I am unsure if I need to add a "sort 4" section or not either.

        INP
        STO NUM1
        INP 
        STO NUM2
        INP
        STO NUM3
        INP 
        STO NUM4
BEGIN   LDA ZERO
        STA INCRE
        LDA NUM2
        SUB NUM1
        BRP SORT2
        LDA ONE
        STO INCRE
        LDA NUM1
        STO PLHOLDER
        LDA NUM2
        LDA PLHOLDER
        STO NUM2
SORT2   LDA NUM3
        SUB NUM2
        BRP SORT3
        LDA ONE
        STO INCRE
        LDA NUM2
        STO PLHOLDER
        LDA NUM3
        STO NUM2
        LDA PLHOLDER
        STO NUM3
SORT3   LDA NUM4
        SUB NUM3
        BRP OUTPUT
        LDA ONE
        STO INCRE
        LDA NUM2
        STO PLHOLDER
        LDA NUM4
        STO NUM3
        LDA PLHOLDER
        STO NUM4
OUTPUT  LDA INCRE
        BRZ NOINCRE
        BRA BEGIN
NOINCRE LDA NUM1
        OUT
        LDA NUM2
        OUT
        LDA NUM3
        OUT
        LDA NUM4
        OUT
        HLT
NUM1    DAT
NUM2    DAT
NUM3    DAT
NUM4    DAT
INCRE   DAT
PLHOLDER DAT
ONE     DAT 001
ZERO    DAT 000

I am using the LMC for this.

Solution

  • The algorithm is fine, but you just have two little, unintended mistakes: the second one is the cause of the infinite loop (for some inputs).

    See the comments in the correction below:

    #input: 4 3 1 2
        INP
        STO NUM1
        INP 
        STO NUM2
        INP
        STO NUM3
        INP 
        STO NUM4
BEGIN   LDA ZERO
        STA INCRE
        LDA NUM2
        SUB NUM1
        BRP SORT2
        LDA ONE
        STO INCRE
        LDA NUM1
        STO PLHOLDER
        LDA NUM2
        STO NUM1    -- was missing
        LDA PLHOLDER
        STO NUM2
SORT2   LDA NUM3
        SUB NUM2
        BRP SORT3
        LDA ONE
        STO INCRE
        LDA NUM2
        STO PLHOLDER
        LDA NUM3
        STO NUM2
        LDA PLHOLDER
        STO NUM3
SORT3   LDA NUM4
        SUB NUM3
        BRP OUTPUT
        LDA ONE
        STO INCRE
        LDA NUM3   -- was wrong
        STO PLHOLDER
        LDA NUM4
        STO NUM3
        LDA PLHOLDER
        STO NUM4
OUTPUT  LDA INCRE
        BRZ NOINCRE
        BRA BEGIN
NOINCRE LDA NUM1
        OUT
        LDA NUM2
        OUT
        LDA NUM3
        OUT
        LDA NUM4
        OUT
        HLT
NUM1    DAT
NUM2    DAT
NUM3    DAT
NUM4    DAT
INCRE   DAT
PLHOLDER DAT
ONE     DAT 001
ZERO    DAT 000

<script src="https://cdn.jsdelivr.net/gh/trincot/lmc@v0.7/lmc.js"></script>

    This also answers your second question:

    I am unsure if I need to add a "sort 4" section or not either.

    No, you don't need another such section. As each section compares two consecutive numbers, you only need 3 when you have an input of 4 numbers.

    Generic solution

    You have tackled the problem of sorting 4 values. But if you are looking for a solution where you can enter a variable number of values and get them sorted, have a look at these answers: