Advanced

Sorting Algorithms

Implementing bubble sort in LC-3 assembly.

Bubble Sort in LC-3

Bubble sort repeatedly steps through the array, comparing adjacent elements and swapping them if they're in the wrong order. It's simple to implement in assembly.

Algorithm:

For i = 0 to n-2:

For j = 0 to n-2-i:

If array[j] > array[j+1], swap them

Repeat until no swaps occur

Let's implement this step by step.

Comparing Two Numbers

To check if A > B, compute A - B and check if the result is positive:

; Compare R0 and R1
; If R0 > R1, branch to GREATER
NOT R2, R1
ADD R2, R2, #1     ; R2 = -R1
ADD R2, R0, R2     ; R2 = R0 - R1
BRp GREATER        ; Branch if R0 > R1

Full Bubble Sort

.ORIG x3000
; Bubble sort an array of 5 numbers
LD R6, STACK

AND R5, R5, #0
ADD R5, R5, #4    ; R5 = n-1 = outer loop count

OUTER
ADD R5, R5, #0
BRz PRINT         ; Done sorting

LEA R1, ARRAY     ; R1 = pointer to array start
ADD R4, R5, #0    ; R4 = inner loop count

INNER
ADD R4, R4, #0
BRz NEXT_OUTER

LDR R2, R1, #0    ; R2 = array[j]
LDR R3, R1, #1    ; R3 = array[j+1]

; Compare: if R2 > R3, swap
NOT R0, R3
ADD R0, R0, #1
ADD R0, R2, R0    ; R0 = R2 - R3
BRnz NO_SWAP

; Swap
STR R3, R1, #0
STR R2, R1, #1

NO_SWAP
ADD R1, R1, #1    ; pointer++
ADD R4, R4, #-1   ; inner count--
BR INNER

NEXT_OUTER
ADD R5, R5, #-1
BR OUTER

; Print sorted array as digits
PRINT
LEA R1, ARRAY
AND R2, R2, #0
ADD R2, R2, #5

PLOOP
ADD R2, R2, #0
BRz DONE
LDR R0, R1, #0
ADD R0, R0, #15
ADD R0, R0, #15
ADD R0, R0, #15
ADD R0, R0, #3
OUT
ADD R1, R1, #1
ADD R2, R2, #-1
BR PLOOP

DONE HALT

ARRAY .FILL #5
      .FILL #2
      .FILL #8
      .FILL #1
      .FILL #4

STACK .FILL xFE00
.END

Bubble sort is O(n²) but easy to implement. For LC-3 programs with small arrays, this is perfectly fine. The focus is on understanding pointer manipulation and nested loops.

← Bit Manipulation