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

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

gnome sort

Gnome sort is a compact O(n²) algorithm to re-arrange a sequence of elements into order. In his article on Gnome sort, Dick Grune describes the algorithm as follows:

Gnome Sort is based on the technique used by the standard Dutch Garden Gnome (Du.: tuinkabouter). Here is how a garden gnome sorts a line of flower pots. Basically, he looks at the flower pot next to him and the previous one; if they are in the right order he steps one pot forward, otherwise he swaps them and steps one pot backwards. Boundary conditions: if there is no previous pot, he steps forwards; if there is no pot next to him, he is done.

The Gnome sort article on Wikipedia describes a slightly modified algorithm.

Implementation in Redcode:

          org    inner

          temp   equ (outer-1)

outer     mov    }p,             temp
p         mov    FIRST+LENGTH-1, {p
          nop    >y,             }p
          mov    temp,           }p
          sne    y,              #LENGTH
          nop    <y,             {p
inner     slt    *p,             {p
y         djn    inner,          #LENGTH-1
          jmn    outer,          y

The redcode implementation is just 9 lines long, and requires 4.5n²-3.5n cycles to sort the sequence in the worse case.

Euclid's algorithm

Euclid's algorithm is used to determine the Greatest Common Divisor of two values. Despite it's simplicity, the only previous redcode implementation I can find is broken.

Implementation in Redcode:

          org    euclid+2

euclid    mod.ab #a,                #b
          mov.x  euclid,            euclid
          jmn.a  euclid,            euclid

parallel processes

This macro uses the preprocessor to generate Redcode which creates a given number of parallel processes.

processes equ 100 ; works for 1 to 1048576
for 20+0*(a=1048576)
for ((processes-1)/(a=a/2))%2==1 && processes>a
spl 1
rof
for ((processes-1)/a)%2==0 && processes>a
mov.i -1,#0
rof
rof

Privacy Policy

Privacy

I respect your privacy. The following policy explains how information is collected on Thoughts on Corewar. Your personal information will never be sold or disclosed to a third party, except where required by law.

Statistics

I use Google Analytics to track aggregate statistics about visitors to Thoughts on Corewar. This information is not linked to personally identifiable information.

Cookies

Cookies are small data files stored by a website on a user's computer. Thoughts on Corewar does not uses cookies. However, some of my advertising partners use cookies.  I have no access to cookies set by advertisers.

Advertisers

I use advertising partners to display ads on Thoughts on Corewar. These partners may use cookies. I work with Google Adsense and Entrecard. I receive a list of Entrecard members who use the 'drop' feature. Please check the advertising partners' websites for their privacy policies.

Contact Information

If you have any questions please contact John Metcalf at digital.wilderness@googlemail.com.

why a new blog?

I've been inspired to create a new blog for two reasons:

1. I love corewar and programming in redcode. I spend far too much of my online time creating websites that provide me with an income. Now I'd like to claim back some of that time for something I enjoy.
2. To show corewar is alive and well in 2008!