Sorting least to greatest of three numbers

CodingWonders90 picture CodingWonders90 · Mar 3, 2013 · Viewed 8.9k times · Source

I am currently learning assembly language. I have been able to create a quick short function to swap two numbers from least to greatest. I am applying the same basic foundation to do this with three numbers but every time I am performing a comparison it goes into an infinite loop. I am declaring this function by using *60. How can I properly sort three numbers from least to greatest? Also, is there a way to have the same function perform sorts of two and three numbers without any additional changes?

Several assembly programs have slight change in syntax. HERE is the link of an educational assembly Little Man computer simulator that I am currently using.

Working Swap with two numbers:

INP     //Input x number
STO 99      //Store x number
INP     //Input y number 
STO 98      //Store y number
BR 60       //Jump to function *60
HLT     //End run
*60         //Number SWAP function
LDA 99      //Load x
STO 87      //Move x to mailbox 87
LDA 98      //Load y
STO 86      //Move y to mailbox 86
SUB 87      //Subtract y - x 
BRP 71      //Branch to line 71 if result is positive
LDA 86      //SUB 87 gives a negative result- then y is smallest number. Load y
OUT     //Display y
LDA 87      //Load x- the greater number. 
OUT     //Display x
HLT     //End here since y > x
LDA 87      //BRP 71 branches here- then x is smallest number 
OUT         //Display x
LDA 86      //y is the greater number
OUT *       //display y 

Answer

Andrew Stollak picture Andrew Stollak · Mar 3, 2013

This is a bubble sort, https://en.wikipedia.org/wiki/Bubble_sort because it uses the swap code three times.

I have never learned Little Man, but based on https://en.wikipedia.org/wiki/Little_man_computer, this should work. I didn't see anything about branching to specific line numbers, but it looks like--based on your first working example--that you've got that down and hopefully can translate the labels appropriately. (fingers crossed)

The Wikipedia entry has several copies of pseudocode, but I wanted to unroll the loops from the first "Optimizing Bubble Sort" pseudocode from the Wikipedia entry because I didn't see anything in Little Man about using indices to access memory locations like you would need for an array. There's no check to see if the array is in order.

Load the three values into registers r91-r93

// loop 1 step 1
if r92-r91>0 then    
    do nothing
else      // swap them, using a temp register  
    temp=r92
    r92=r91
    r91=temp
end if
// loop 1 step 2
if r93-r92>0 then 
    do nothing
else      // swap them, using a temp register 
    temp=r93
    r93=r92 
    r92=temp
end if 
// loop 2 step 1
if r92-r91>0 then 
    do nothing
else      // swap them, using a temp register  
    temp=r92
    r92=r91
    r91=temp
end if

Write out the registers in order:  r91, r92, r93

Here's the same code in my best approximation of Little Man, according to the Wikipedia article. You might need to fix the labels.

         INP        // Read in the first value
         STA 91     // store it
         INP        // Read in the second value
         STA 92     // store it
         INP        // Read in the third value
         STA 93     // store it
         LDA 92     // LOOP 1, STEP 1:  
         SUB 91     // 
         BRP STEP2  // if r91 and r92 are in order, don't swap them
         LDA 92     // Begin swapping registers
         STA 99     // temp = r92
         LDA 91
         STA 92     // r92 = r91
         LDA 99
         STA 91     // r91 = temp
STEP2    LDA 93     // LOOP 1, STEP 2
         SUB 92
         BRP STEP3  // If r92 and r93 are in order, don't swap them
         LDA 93     // Begin swapping registers
         STA 99     // temp = r93
         LDA 92
         STA 93     // r93 = r92
         LDA 99
         STA 92     // r92 = temp
STEP3    LDA 92     // LOOP 2, STEP 1
         SUB 91
         BRP STEP4  // if r91 and r92 are in order, don't swap them
         LDA 92     // Begin swapping registers
         STA 99     // temp = r92
         LDA 91
         STA 92     // r92 = r91
         LDA 99
         STO 91     // r91 = temp
STEP4    LDA 91     // Write out the sorted values 
         OUT
         LDA 92
         OUT
         LDA 93
         OUT
         HLT        // stop