Monday 25 February 2008

Bubble sort

Bubble sort is an O(n²) algorithm to sort a sequence of elements into order. Ilmari Karonen's Bubbly Sort 1b is a 10 line implementation of Bubble sort which requires 3.5n²-0.5n-4 cycles in the worst case.

My alternative code is shown below:

Implementation in Redcode:
          org    inner

temp equ (outer-1)

outer mov.b x, y
mov.f q, p

inner slt {p, <p
y djn inner, #LENGTH-1
jmz next, y

mov @p, temp
p mov FIRST+LENGTH, FIRST+LENGTH-1
mov temp, *p
djn inner, y
x
next djn outer, #LENGTH-1

q dat FIRST+LENGTH-p, FIRST+LENGTH-p-1
This alternative implementation runs slightly faster than Ilmari's, at the cost of 1 extra line of code. The number of cycles in the worst case is 3n²-5, which also beats Gnome sort.

No comments: