Crystal Reports 9: Gnome Sort

Crystal Reports 9 provides no way to sort an array. If you want to calculate the median value for an array, it must be sorted. On the other hand, it does provide comparisons that work properly based on data type, so that for example ( "Alice" < "Bethany" ) will evaluate true. The following examples are designed to sort numerical arrays but they can as easily sort strings or any other data types in Crystal.

One sort method that is very easy to implement is a Gnome Sort. Its execution time is halfway between an insertion sort and a bubble sort; it performs better than bubble sort on pre-sorted lists. Crystal allows only very small numbers (in a programming sense) of iterations in loops, so a bubble sort can only be used to sort small lists. A gnome sort will sort slightly longer lists.

First, the psuedocode, as provided by WikiPedia:

function gnomeSort(a[1..size]) {
 i := 2
 while i = size
   if a[i-1] = a[i]
       i := i + 1
   else
       swap a[i-1] and a[i]
       i := i - 1
       if i = 0
         i := 1
}

This is well and good, but how does it translate to Crystal? Like this:

Shared NumberVar Array foo;
Local NumberVar Array bar := foo;
Local NumberVar i := 2;
Local NumberVar temp_value;
while ( i < ( ubound(bar) + 1 ))
do
(
  if ( bar [i - 1] <= bar [i] )
  then
    i := i + 1
  else
  (
     temp_value := bar [i - 1];
     bar [i - 1] := bar [i];
     bar [i] := temp_value;
     i := i - 1;
     if ( i < 2 ) then i := 2;
  );
);
foo := bar;

This example (pulled directly from a working report, and decommented for formatting) pulls in a shared array called foo, and assigns it to a local array called bar. Since Crystal inexplicably starts numbering arrays where the first element is referred to as 1, our offset variable (Local NumberVar i) starts at 2, rather than 1 as in the psuedocode example. There is also a temporary storage variable (Local NumberVar temp_value) that holds the value being moved towards the end of the list.

In simple english, until reaching the end of the array (the while loop) we check to see if the previous value (i - 1) is less than or equal to the current value (i). If it is, then we increment i and don't do anything else, which means the next time the loop goes around, we'll be looking at the next pair of values. If it isn't, meaning that the two values are out of order, they are flipped, we go back one position unless we are already at the beginning, and then we loop again.

A sample report is available that illustrates this sort algorithm with working examples (including the above formula.)