Most efficient way to sort parallel arrays in a restricted-feature language

Question

The environment: I am working in a proprietary scripting language where there is no such thing as a user-defined function. I have various loops and local variables of primitive types that I can create and use.

I have two related arrays, "times" and "values". They both contain floating point values. I want to numerically sort the "times" array but have to be sure that the same operations are applied on the "values" array. What's the most efficient way I can do this without the benefit of things like recursion?

Answer 1

Just take your favourite sorting algorithm (e.g. Quicksort or Mergesort) and use it to sort the "values" array. Whenever two values are swapped in "values", also swap the values with the same indices in the "times" array.

So basically you can take any fast sorting algorithm and modify the swap() operation so that elements in both arrays are swapped.

Answer 2

Take a look at the Bottom-Up mergesort at Algorithmist. It's a non-recursive way of performing a mergesort. The version presented there uses function calls, but that can be inlined easily enough.

Like martinus said, every time you change a value in one array, do the exact same thing in the parallel array.

Here's a C-like version of a stable-non-recursive mergesort that makes no function calls, and uses no recursion.

const int arrayLength = 40;
float times_array[arrayLength];
float values_array[arrayLength];

// Fill the two arrays....

// Allocate two buffers
float times_buffer[arrayLength];
float values_buffer[arrayLength];
int blockSize = 1;

while (blockSize <= arrayLength)
{
 int i = 0;
 while (i < arrayLength-blockSize)
 {
  int begin1 = i;
  int end1 = begin1 + blockSize;
  int begin2 = end1;
  int end2 = begin2 + blockSize;

  int bufferIndex = begin1;
  while (begin1 < end1 && begin2 < end2)
  {
   if ( values_array[begin1] > times_array[begin2] )
   {
    times_buffer[bufferIndex] = times_array[begin2];
    values_buffer[bufferIndex++] = values_array[begin2++];
   }
   else
   {
    times_buffer[bufferIndex] = times_array[begin1];
    values_buffer[bufferIndex++] = values_array[begin1++];
   }
  }
  while ( begin1 < end1 )
  {
   times_buffer[bufferIndex] = times_array[begin1];
   values_buffer[bufferIndex++] = values_array[begin1++];
  }
  while ( begin2 < end2 )
  {
   times_buffer[bufferIndex] = times_array[begin2];
   values_buffer[bufferIndex++] = values_array[begin2++];
  }

  for (int k = i; k < i + 2 * blockSize; ++k)
  {
   times_array[k] = times_buffer[k];
   values_array[k] = values_buffer[k];
  }

  i += 2 * blockSize;
 }
 blockSize *= 2;
}

Answer 3

You could maintain an index table and sort the index table instead.

This way you will not have to worry about times and values being consistent.

And whenever you need a sorted value, you can lookup on the sorted index.

And if in the future you decided there was going to be a third value, the sorting code will not need any changes.

Here's a sample in C#, but it shouldn't be hard to adapt to your scripting language:

static void Main() {

    var r = new Random();

    // initialize random data
    var index = new int[10];      // the index table
    var times = new double[10];   // times 
    var values = new double[10];  // values

    for (int i = 0; i < 10; i++) {
        index[i] = i;
        times[i] = r.NextDouble();
        values[i] = r.NextDouble();
    }

    // a naive bubble sort
    for (int i = 0; i < 10; i++)
        for (int j = 0; j < 10; j++)

            // compare time value at current index
            if (times[index[i]] < times[index[j]]) {

                // swap index value (times and values remain unchanged)
                var temp = index[i];
                index[i] = index[j];
                index[j] = temp;
            }

    // check if the result is correct
    for (int i = 0; i < 10; i++)
        Console.WriteLine(times[index[i]]);

    Console.ReadKey();

}

Note: I used a naive bubble sort there, watchout. In your case, an insertion sort is probably a good candidate. Since you don't want complex recursions.