Natural Blogarithms

It hasn’t been since I was taking Computer Science courses during my Master’s work that I had the chance to really look at sorting algorithms. But I’ve always just fascinated by them. There are some really creative ways to take a list of numbers (usually a very long list) and put all of them in order. Here is one I passed on to a student to use for a quick application as part of a larger project:

Gnome Sort

From Wiki:  (http://en.wikipedia.org/wiki/Gnome_sort)

Gnome sort is a sort algorithm which is similar to insertion sort except that moving an element to its proper place is accomplished by a series of swaps, as in bubble sort. The name comes from the supposed behavior of the Dutch garden gnome in sorting a line of flowerpots. It is conceptually simple, requiring no nested loops. The running time is O(n²), and in practice the algorithm has been reported to run slightly slower than bubble sort, although this depends on the details of the architecture and the implementation.

From  vrije Universiteit amsterdame (Computer Science Department Website)
(http://www.cs.vu.nl/~dick/gnomesort.html)

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.

C – implementation

void gnomesort(int n, double * ar)
{
      int i = 0;
      while(i<n){
            if (i==0 || ar[i-1] <= ar[i]) i++;
            else {double tmp = ar[i]; ar[i] = ar[i-1]; ar[--i] = tmp;}
      }
}

Trackback URI | Comments RSS