## Wednesday, 27 February 2008

### 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,             tempp         mov.ba #FIRST+LENGTH-1,#FIRST+LENGTHinner     slt    <p,             *p          mov.ba p,              py         djn    inner,          #LENGTH-1          add.b  x,              p          mov    *p,             @p          mov    temp,           *px         djn    outer,          #LENGTH-1`

## 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,              pinner     slt    {p,             <py         djn    inner,          #LENGTH-1          jmz    next,           y          mov    @p,             tempp         mov    FIRST+LENGTH,   FIRST+LENGTH-1          mov    temp,           *p          djn    inner,          yxnext      djn    outer,          #LENGTH-1q         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.

## Tuesday, 19 February 2008

### 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,           tempinner     slt    {p,             <py         djn    inner,          #LENGTH-(LENGTH*ra/rb)          jmz    done,           y          mov    @p,             tempp         mov    FIRST+LENGTH,   FIRST+LENGTH-(LENGTH*ra/rb)          mov    temp,           *p          djn    inner,          ydone      mul    #ra,            gapgap       div    #rb,            #(LENGTH*ra/rb)          jmn    outer,          gap          nop    >gap,           {outer          jmn    outer,          tempq         dat    FIRST+LENGTH-p, FIRST+LENGTH-p`

## Tuesday, 12 February 2008

### 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-1outer     mov    p,              <stack          mov    {p,             pivotinner     slt    pivot,          >py         djn    inner,          #LENGTH-1          jmz    done,           y          mov    <p,             *p          mov    {p,             @p          djn    inner,          ydone      mov.a  @stack,         p          mov.ba p,              @stack          mov    pivot,          >pqsort     mov.ab p,              y          sub.b  p,              y          slt    y,              #2          jmp    outer,          <y          mov.f  >stack,         p          jmn    qsort,          pp         dat    FIRST+LENGTH,   FIRST`