Thursday, 31 January 2008

stooge sort

Stooge sort is discussed in Cormen, Leiserson, Rivest and Stein's Introduction to Algorithms. Wikipedia's article on Stooge sort describes the algorithm as follows:

  • If the value at the end is smaller than the value at the start, swap them.
  • If there are 3 or more elements in the current list subset,
    • Stooge sort the initial 2/3 of the list
    • Stooge sort the final 2/3 of the list
    • Stooge sort the initial 2/3 of the list again
Stooge sort is extremely inefficient. For example, sorting 100 elements requires in the region of 2.4 million cycles compared to around 3500 for quicksort and 8000 for insertion sort.

Implementation in Redcode:
          org    inner

stack equ outer-2
temp equ outer-1

outer mov p, <stack
sub.ba temp, @stack
mov p, <stack
add.b temp, @stack
sub.ba temp, p
inner slt {p, @p
jmp noexch, }p

mov @p, temp
p mov FIRST+LENGTH, FIRST
mov temp, }p

noexch mov.ab p, temp
sub.b p, temp
div #3, temp
jmn outer, temp

finished mov.f >stack, p
jmn inner, p

1 comment:

John | Thoughts on Corewar... said...

There's a potential improvement to the algorithm:

Only resort the initial 2/3 if a change is made when the final 2/3 is sorted.

Are any other improvements possible?