Tutorial: Sorting your Data

I was posed a question earlier this week: given an arbitrary English text, how would you pick out the 10 most common words?  On the NXT,  having a pile of sensor readings is nice but what if you need to pick the top 10 smallest or biggest ones?  How would you go about doing that?  There are no intrinsic functions for this sort of thing in ROBOTC. That started me off doing a little research into the different algorithms out there.  Now, I am no mathematician but far more visually inclined.  I remember these really cool Java demos I saw years and years ago, which showed the data being sorted in your browser as the algorithms made their passes through the data.  I thought it would be really cool if I could do the same thing in ROBOTC.  And so I did.

Bubble sort

This is the first one I implemented because I thought it looked cool.  I found a really nice explanation of it here: [LINK].  How does it work?  Imagine a pile of random data and allowing the largest value to “bubble” up to the top.  You do this by comparing one element to the one next to it, until they’re in proper ascending order.  You repeat this whole thing, until you’ve sorted all of the elements in the array.

The code for this is pretty simple:

for(int i = 0; i < MAX_NUMBERS; i++)
{
  for(int j = 0; j < (MAX_NUMBERS - 1); j++)
  {
    if (arr[j] > arr[j+1])
    {
      temp = arr[j];
      arr[j] = arr[j+1];
      arr[j+1] = temp;
    }
  }
}

The only problem with this one is that it’s pretty slow.  It has an O(n²) worse case complexity, which means that it gets exponentially less efficient as the data set increases in size.  That means that a set of 11 sensor readings will typically perform about 20% worse than one with 10.  A data set with 50 readings will perform 25 times worse than one with 10 in a worse-case scenario.

Shell sort

In my test program, this was actually the last one I implemented and the Wiki page was pretty terrifying until I found a more friendly page with a nice implementation.  I found a good explanation of how it worked here: [LINK].

Instead of comparing adjacent elements, like the bubble sort, the shell sort repeatedly compares elements that are a certain distance away from each other (m presents this distance).  The value of m tarts out as half the input size and is halved after each pass through the array.  The elements are compared and swapped when needed.

In code, that ends up looking a bit like this:

for(m = MAX_NUMBERS/2 ; m > 0; m /= 2)
{
  for(j = m; j < MAX_NUMBERS; j++)
  {
    for(i = j - m; i >= 0; i -= m)
    {
      if(arr[i + m] >= arr[i])
        break;
      else
      {
        mid = arr[i];
        arr[i] = arr[i + m];
        arr[i + m] = mid;
      }
    }
  }
}

In the table below you can see how it works.  Since we have 6 elements, the initial distance is 3.

Insertion sort

This is a really terrible sorting algorithm but I included it to give you an idea of what a difference it can make when you pick the wrong sorting algorithm.  This is the code for it:

for (i = 1 ; i < MAX_NUMBERS ; i++ )
{
  for (j = 0 ; j < i ; j++ )
  {
    if ( arr[j] > arr[i] )
    {
      temp = arr[j] ;
      arr[j] = arr[i] ;

      for (k = i ; k > j ; k-- )
      {
        arr[k] = arr[k - 1] ;
      }
      arr[k + 1] = temp ;
    }
  }
}

I am showing the temp variable here as well due to the way it does some additional sorting while holding that value aside.

Demo program

As I said in the beginning, I am a very visually oriented person, so I’ve made a small video of my sorting program.

You can download the source code here: [LINK].  Enjoy!

Top one, nice one, get sorted!