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.
Bubblesort
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
>0
start:
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
>16
is_sorted:
LOAD A has_swapped ; check if the swapped bool changed
ISZERO A
JZ exit ; goto exit
JMP restart_loop ; goto restart loop
>32
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
>80
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
>95
store_reg:
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
>112
swap_val:
STORE A has_swapped ; swapped = true
SWAP A B
JMP store_reg ; goto store registers
; 255 - EXIT
>255
exit:
HALT
; DATA
>160
$5
$4
$3
$2
$1
>176
c_len: $4
c_i: $160
c_j: $161
>192
len: $0
i: $0
j: $0
has_swapped: $0
