Sorting and Arrays with Q8

To introduce a little more complexity and explore some of the cooler features of Q8, we are going to write a simple sort. Bubblesort! It may be slow, but it's easy to understand, and easy enough to implement.


In bubblesort, each element is compared with its neighbor and swapped if necessary. Unfortunately, it can't always sort the whole array in one pass. It must keep running until all of the elements have slowly made their way to their correct positions. Worst-case, the elements are sorted, but in the opposite direction of the desired sort, it takes the length of the array, n, times the the number of passes necessary to fix it, in this case, equal to the length of the array, n. That leaves the runtime at a miserable worst-case of n2. With a larger array, this can get really ridiculous.

Main Loop - With Swap: 36 tiles
Main Loop - Without Swap: 31 tiles
Main Loop - Average: 33.5 tiles
Restart Loop: 24 tiles
n, our array length for this example is 5

Main Loop gets called once per element, so n times per sort iteration
Restart Loop gets called once per array walk, so average of n/2 times

Main Loop average * n * Restart Loop * (n/2) = ~10,050 tiles
Main Loop worst-case * n * Restart Loop * n = ~21,600 tiles
Main Loop best-case * n * Restart Loop * 1 = ~3,720 tiles (Loop is already sorted)

Assuming each tile takes 1 second, best case runs in 1 hour, 2 minutes, and worst case runs in 6 hours. n2 time is not ideal. Bubblesort is more useful as a teaching tool than as a sort to use for practical applications.

C-like Program

int len = 5;
int array[len] = {5, 4, 3, 2, 1};
bool swapped = true;

while (swapped) {
    swapped = false;
    for (int i = 0; i < len - 1; i++) {
	    int j = i + 1;
        if (array[j] > array[i]) {
            swap(array, i, j);
            swapped = true;

Bytecode Program

Assembly Program

; Copy the starting indices and array length for later
LOAD A c_i ; index: i
LOAD B c_j ; index + 1: j
STORE A i ; use as initial i
STORE B j ; use as initial j
LOAD A c_len ; len - 1
STORE A len ; use as initial len
JMP main_loop ; goto main loop

LOAD A has_swapped ; check if the swapped bool changed
JZ exit ; goto exit
JMP restart_loop ; goto restart loop

LOAD A len ; grab len - 1
STORE A c_len ; use as new remaining distance
LOAD A i ; grab initial i
LOAD B j ; grab initial j
STORE A c_i ; use as new i
STORE B c_j ; use as new j
SET A 0 ; swapped = false
STORE A has_swapped ; use as new swapped
JMP main_loop ; goto main loop

LOAD A c_len ; grab remaining distance to end of list
ISZERO A ; Are we all the way through the list?
JZ is_sorted ; goto is sorted?
DEC A ; remaining distance--
STORE A c_len ; store new distance
LOADI A c_i ; load i
LOADI B c_j ; load j
CMP A B ; compare i and j
JG swap_val ; goto swap values if necessary

STOREI A 177 ; store A at grid[i]
STOREI B 178 ; store B at grid[j]
LOAD A c_i ; load i
LOAD B c_j ; load j
INC A ; i++
INC B ; j++
STORE A c_i ; update i
STORE B c_j ; update j
JMP main_loop ; goto main loop

STORE A has_swapped ; swapped = true
JMP store_reg ; goto store registers

; 255 - EXIT


c_len: $4
c_i: $160
c_j: $161
len: $0
i: $0
j: $0
has_swapped: $0