Human Resource Machine/Year 41

Strategy

Bubble sort

Compare pairs of items moving from start to end and swap if the are not in order. After each iteration the largest value is pushed to the end of list. After total of N-1 iterations, the list is sorted. Very simple but inefficient algorithm.

Size: 33; Length: 928

    JUMP     d
a:
b:
    COPYFROM [20]
    JUMPZ    c
    OUTBOX  
    BUMPUP   20
    JUMP     b
c:
d:
    COPYFROM 24
    COPYTO   20
e:
    INBOX   
    COPYTO   [20]
    JUMPZ    f
    BUMPUP   20
    JUMP     e
f:
g:
    BUMPDN   20
    JUMPZ    a
    COPYFROM 24
    COPYTO   21
    COPYTO   22
    JUMP     j
h:
    COPYFROM [21]
    COPYTO   23
    COPYFROM [22]
    COPYTO   [21]
    COPYFROM 23
    COPYTO   [22]
i:
    BUMPUP   21
    SUB      20
    JUMPZ    g
j:
    BUMPUP   22
    COPYFROM [22]
    SUB      [21]
    JUMPN    h
    JUMP     i

Insertion sort

Go through each item and insert into previously sorted section. After each iteration a larger section at the start or end of list is sorted. After total of N-1 iterations list is sorted.

Size: 32; Length: 704

    COPYFROM 24
a:
    COPYTO   23
b:
    INBOX   
    COPYTO   [23]
    JUMPZ    c
    BUMPUP   23
    JUMP     b
c:
    COPYTO   21
d:
    BUMPUP   21
    COPYTO   22
    COPYTO   19
    COPYFROM [21]
    JUMPZ    h
    COPYTO   20
e:
    BUMPDN   22
    JUMPN    f
    COPYFROM 20
    SUB      [22]
    JUMPN    g
f:
    COPYFROM 20
    COPYTO   [19]
    JUMP     d
g:
    COPYFROM [22]
    COPYTO   [19]
    BUMPDN   19
    JUMP     e
h:
    COPYTO   21
i:
    COPYFROM [21]
    JUMPZ    a
    OUTBOX  
    BUMPUP   21
    JUMP     i

Optimizing size

Performing the iteration sort from the end of the list and doing each swap individually saves a single command.

Size: 31; Length: 710

    JUMP     d
a:
b:
    COPYFROM [20]
    JUMPZ    c
    OUTBOX  
    BUMPUP   20
    JUMP     b
c:
d:
    COPYFROM 24
    COPYTO   20
e:
    INBOX   
    COPYTO   [20]
    JUMPZ    f
    BUMPUP   20
    JUMP     e
f:
g:
h:
    BUMPDN   20
    JUMPZ    a
    COPYTO   21
    COPYTO   22
    BUMPDN   21
    JUMP     j
i:
    COPYFROM [21]
    COPYTO   [22]
    COPYFROM 23
    COPYTO   [21]
    BUMPUP   21
    BUMPUP   22
j:
    COPYFROM [22]
    JUMPZ    h
    COPYTO   23
    SUB      [21]
    JUMPN    i
    JUMP     g

Optimizing Length

Performing iteration sort from the end and reusing counters saves on length.

Size: 32; Length: 673

   JUMP     d
a:
b:
    COPYFROM [20]
    JUMPZ    c
    OUTBOX  
    BUMPUP   20
    JUMP     b
c:
d:
    COPYFROM 24
    COPYTO   20
e:
    INBOX   
    COPYTO   [20]
    JUMPZ    h
    BUMPUP   20
    JUMP     e
f:
g:
    COPYFROM 23
    COPYTO   [21]
h:
    BUMPDN   20
    JUMPZ    a
    COPYTO   21
    COPYTO   22
    BUMPDN   21
    COPYFROM [21]
    COPYTO   23
    JUMP     j
i:
    COPYFROM [22]
    COPYTO   [21]
    BUMPUP   21
    BUMPUP   22
j:
    COPYFROM [22]
    JUMPZ    g
    SUB      23
    JUMPN    i
    JUMP     f