Sunday 20 January 2008

insertion sort

Insertion sort is an algorithm to arrange a sequence of elements into order. Elements are removed one by one from the unsorted sequence and inserted into the correct position in a new, sorted sequence.

For the worst case the Redcode Insertion sort requires 1.5n²+5.5n-7 cycles to sort n elements.

Implementation in Redcode:
          org    outer

temp equ (outer-1)

outer nop }z, {q
z mov #0, y
q mov.a #FIRST+LENGTH-p,p
p mov #0, #0
mov {p, temp
inner slt @p, temp
jmp found
mov >p, }p
y djn inner, #0
found mov temp, *p
djn outer, #LENGTH-1

No comments: