Bubble Sort

This advanced example demonstrates bubble sort: a classic sorting algorithm that sorts an array in memory.

Overview

Difficulty: Advanced

Concepts: Nested loops, memory operations, array manipulation, pseudo-random number generation

Output: Sorted array at RAM[0x60..0x7F] (32 bytes in ascending order)

The Program

 1; Bubble Sort - Generate and sort 32 random bytes in ascending order
 2; Uses PRNG to fill RAM[0x60..0x7F], then bubble sorts in place
 3; Output: Sorted array at RAM[0x60..0x7F]
 4
 5    ; Initialize PRNG and counters
 6    ldi r16, 0x60     ; Base address
 7    ldi r17, 0        ; Index
 8    ldi r18, 123      ; PRNG seed
 9    ldi r25, 75       ; PRNG multiplier
10
11init_loop:
12    ; Generate random byte: seed = (seed * 75) + 1
13    mul r18, r25
14    inc r18
15    
16    st r16, r18       ; Store random value
17    inc r16
18    inc r17
19    
20    ldi r23, 32
21    cp r17, r23
22    brne init_loop
23
24    ; Bubble sort: 32 elements
25    ldi r18, 0        ; Outer loop: i = 0
26
27outer_loop:
28    ldi r19, 0        ; Inner loop: j = 0
29
30inner_loop:
31    ; Load pair: A = RAM[0x60 + j], B = RAM[0x60 + j + 1]
32    ldi r20, 0x60
33    add r20, r19
34    ld r21, r20       ; r21 = A
35    
36    ldi r22, 0x60
37    add r22, r19
38    ldi r23, 1
39    add r22, r23
40    ld r24, r22       ; r24 = B
41    
42    ; Swap if A > B (ascending order)
43    cp r21, r24
44    brcs no_swap      ; Skip if A < B
45    st r20, r24       ; RAM[addr_A] = B
46    st r22, r21       ; RAM[addr_B] = A
47
48no_swap:
49    inc r19
50    ldi r23, 31
51    cp r19, r23
52    breq end_inner
53    jmp inner_loop
54
55end_inner:
56    inc r18
57    ldi r23, 31
58    cp r18, r23
59    breq done
60    jmp outer_loop
61
62done:
63    jmp done

Algorithm Overview

The program has two main phases:

  1. Initialization: Generate 32 pseudo-random values and store them in RAM

  2. Bubble Sort: Sort the array using the bubble sort algorithm

Phase 1: Array Initialization

Pseudo-Random Number Generator

The program uses a simple linear congruential generator (LCG):

seed(n+1) = (seed(n) × 75) + 1

This generates a sequence of pseudo-random 8-bit values.

ldi r18, 123      ; PRNG seed (starting value)
ldi r25, 75       ; PRNG multiplier

init_loop:
    mul r18, r25  ; multiply seed by 75
    inc r18       ; add 1
    st r16, r18   ; store at RAM[base + index]
    ; ...

After 32 iterations, RAM[0x60..0x7F] contains pseudo-random values.

Phase 2: Bubble Sort

Algorithm Explanation

Bubble sort works by repeatedly stepping through the array, comparing adjacent elements, and swapping them if they’re in the wrong order.

for i = 0 to n-2:
    for j = 0 to n-2:
        if array[j] > array[j+1]:
            swap(array[j], array[j+1])

Outer Loop

ldi r18, 0        ; i = 0
outer_loop:
    ; ... inner loop ...
    inc r18
    ldi r23, 31
    cp r18, r23
    breq done
    jmp outer_loop

Runs 31 times (i = 0 to 30).

Inner Loop

ldi r19, 0        ; j = 0
inner_loop:
    ; load element A = RAM[0x60 + j]
    ldi r20, 0x60
    add r20, r19
    ld r21, r20     ; r21 = A

    ; load element B = RAM[0x60 + j + 1]
    ldi r22, 0x60
    add r22, r19
    ldi r23, 1
    add r22, r23
    ld r24, r22     ; r24 = B

    ; compare and swap if A > B (for ascending order)
    cp r21, r24
    brcs no_swap    ; skip if A < B
    st r20, r24     ; swap: RAM[addr_A] = B
    st r22, r21     ; swap: RAM[addr_B] = A

no_swap:
    inc r19
    ; ...

For each j:

  1. Load adjacent elements (j and j+1)

  2. Compare them

3. Swap if first > second (for ascending order) 3. Swap if first > second 4. Advance to next pair

Register Usage

Register Allocation

Register

Purpose

R16

Memory address pointer / base address

R17

Array index during initialization

R18

PRNG seed / outer loop counter (i)

R19

Inner loop counter (j)

R20

Address of element A

R21

Value of element A

R22

Address of element B

R23

Temporary comparison value

R24

Value of element B

R25

PRNG multiplier constant (75)

Memory Layout

┌──────────────────────────────────┐
│ Address  │ Content               │
├──────────┼───────────────────────┤
│ 0x0060   │ Random value 1        │
│ 0x0061   │ Random value 2        │
│ 0x0062   │ Random value 3        │
│   ...    │   ...                 │
│ 0x007F   │ Random value 32       │
└──────────────────────────────────┘

After sorting: values in ascending order

Execution Example

Initial Array (pseudo-random)

[123, 78, 234, 45, 190, 67, 12, 198, ...]

After Bubble Sort

[12, 45, 67, 78, 123, 190, 198, 234, ...]

Bubble sort compares and swaps adjacent elements until the entire array is sorted.

Running the Example

Interactive Debugger

tiny8 examples/bubblesort.asm

Watch the sorting process step-by-step. Set marks at the beginning of inner_loop to track passes.

Animation

tiny8 examples/bubblesort.asm -m ani -o bubblesort.gif \
    --mem-start 0x60 --mem-end 0x7F

Creates a visualization showing:

  • Memory heatmap of the array being sorted

  • Register changes during comparisons

  • Visual pattern of values moving to their correct positions

Python API

from tiny8 import CPU, assemble_file

cpu = CPU()
cpu.load_program(assemble_file("examples/bubblesort.asm"))
cpu.run(max_steps=50000)  # Bubble sort needs many steps!

# Read sorted array
sorted_array = [cpu.read_ram(i) for i in range(0x60, 0x80)]
print("Sorted array:", sorted_array)

# Verify it's sorted in ascending order
assert all(sorted_array[i] <= sorted_array[i+1]
           for i in range(len(sorted_array)-1))
print("✓ Array is correctly sorted!")

Performance Analysis

Time Complexity

  • Best case: O(n²) - 31 × 31 = 961 comparisons

  • Worst case: O(n²) - Same as best (this implementation doesn’t optimize)

  • Average case: O(n²)

For 32 elements:

  • Outer loop: 31 iterations

  • Inner loop: 31 iterations per outer

  • Total comparisons: ~961

  • Total swaps: Variable (depends on initial order)

Instruction Count

Each comparison involves approximately:

  • 10 instructions to load addresses and values

  • 5 instructions for comparison and potential swap

  • 3 instructions for loop control

Total: ~15,000+ instructions for a complete sort.

Key Concepts

Nested Loops

Two loop counters working together:

outer_loop:
    ldi r19, 0
    inner_loop:
        ; ... work ...
        inc r19
        ; ... inner loop test ...
    inc r18
    ; ... outer loop test ...

Address Calculation

Computing memory addresses dynamically:

ldi r20, 0x60     ; Base address
add r20, r19      ; Add offset
ld r21, r20       ; Load from computed address

Conditional Swapping

cp r21, r24       ; Compare values (A vs B)
brcs no_swap      ; Skip swap if A < B (already in order)
st r20, r24       ; Perform swap: RAM[A] = B
st r22, r21       ; Perform swap: RAM[B] = A
no_swap:

Exercises

  1. Count swaps: Add a counter to track number of swaps

  2. Optimize: Add early exit if no swaps occurred in a pass

  3. Different sizes: Sort 16 or 64 elements instead

  4. Descending order: Modify to sort in descending order

  5. Different algorithm: Implement selection sort or insertion sort

Solutions Hints

Count swaps: Add inc r26 in the swap section, initialize R26 to 0.

Optimize: Set a flag when swapping, check it at end of outer loop.

Descending order: Change brcs no_swap to brcc no_swap.

Visualization Tips

When viewing the animation:

  • Memory panel: Watch values “bubble” to their positions

  • Register panel: R19 (j) cycles 0-30 repeatedly

  • Register panel: R18 (i) increments slowly

Look for:

  • Large values moving right (higher addresses)

  • Small values moving left (lower addresses)

  • Progressively fewer changes as array becomes sorted

Comparison with Other Sorts

Sorting Algorithm Comparison

Algorithm

Time Complexity

Space

Stability

Bubble Sort

O(n²)

O(1)

Yes

Selection Sort

O(n²)

O(1)

No

Insertion Sort

O(n²)

O(1)

Yes

Quick Sort

O(n log n)

O(log n)

No

Bubble sort is chosen for this example because it’s conceptually simple and demonstrates memory operations clearly.