selection sort

Selection sort in an algorithm which sorts a sequence of elements. The smallest element is removed from the sequence and added to the end of a new sorted sequence. This continues until all elements have been moved to the new sequence.

Selection sort is an O(n²) algorithm. The redcode implemention is 10 instructions long and requires 1.5n²+5.5n-8 cycles in the worst case, making it approximately twice as fast as Bubble Sort.

Implementation in Redcode:

          org    outer+1

          temp   equ (outer-1)

outer     mov.b  x,              y
          mov    <p,             temp
p         mov.ba #FIRST+LENGTH-1,#FIRST+LENGTH
inner     slt    <p,             *p
          mov.ba p,              p
y         djn    inner,          #LENGTH-1
          add.b  x,              p
          mov    *p,             @p
          mov    temp,           *p
x         djn    outer,          #LENGTH-1

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.

Comb sort

Comb sort (also known as Dobosiewicz sort) makes a number of passes through a sequence of elements, exchanging any elements which are out of order. With each pass the distance between compared elements decreases. The algorithm terminates when all elements are in order.

In the redcode implementation, the value of the temp element is used as a flag to determine whether or not any exchanges occurred in the last pass.

Implementation in Redcode:

          ra     equ 4
          rb     equ 5

          org    inner

          temp   equ (outer-1)

outer     mov    #LENGTH,        y
          sub.b  gap,            y
          mov.f  q,              p
          sub.b  gap,            p
          sub    temp,           temp

inner     slt    {p,             <p
y         djn    inner,          #LENGTH-(LENGTH*ra/rb)
          jmz    done,           y

          mov    @p,             temp
p         mov    FIRST+LENGTH,   FIRST+LENGTH-(LENGTH*ra/rb)
          mov    temp,           *p
          djn    inner,          y

done      mul    #ra,            gap
gap       div    #rb,            #(LENGTH*ra/rb)

          jmn    outer,          gap
          nop    >gap,           {outer
          jmn    outer,          temp

q         dat    FIRST+LENGTH-p, FIRST+LENGTH-p

Quicksort

Quicksort is an algorithm developed by C. A. R. Hoare in 1960 to sort a sequence of elements into order. Quicksort works by dividing a sequence into two sub-sequences.

An element is selected from the sequence and called the pivot. The sequence is then re-arranged so all elements with a value less than the pivot are before the pivot and all elements with a greater value are after it.

The sub-sequences before and after the pivot are then recursively sorted.

Implementation in Redcode:

          org    qsort

          stack  equ outer-2
          pivot  equ outer-1

outer     mov    p,              <stack
          mov    {p,             pivot

inner     slt    pivot,          >p
y         djn    inner,          #LENGTH-1
          jmz    done,           y
          mov    <p,             *p
          mov    {p,             @p
          djn    inner,          y

done      mov.a  @stack,         p
          mov.ba p,              @stack
          mov    pivot,          >p

qsort     mov.ab p,              y
          sub.b  p,              y

          slt    y,              #2
          jmp    outer,          <y

          mov.f  >stack,         p
          jmn    qsort,          p

p         dat    FIRST+LENGTH,   FIRST

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.