Algorithm design for comparing split times in a race

Question

I need to determine the ranking of values in an array without altering their position, so that I can print the position of each split time next to the actual value of the split time in a table like so.

<table>
<tr>
  <th>Split 1</th>
  <th>Split 2</th>
  <th>Split 3</th>
</tr>
<tr>
  <td>4.66 (1)</td>
  <td>5.12 (3)</td>
  <td>4.75 (2)</td>
</tr>
</table>

My array = [4.66, 5.12, 4.75] and I need to iterate through it and print the rank rank as seen in parenthesis above. I can't sort, because I need to do this for several decimals in the html table. Any suggestions for implementing this algorithm?

Answer 1

Use quicksort (or the sorting algorithm of your choice) to sort a list of array indexes according to the corresponding split times. The array of indexes is a proxy for the array of split times. We don't want to change the order of the times, but we want to know what the order of the times would be if we sorted it.

Given split time array: splits[] = {4.2, 3.9, 4.1, 3.8, 3.7}

We start with an array of indices: indexes[] = {0, 1, 2, 3, 4}

Now we sort indexes array using the values from splits. Any sorting algorithm needs a comparison function, and ours is:

compare(i, j) := if splits[i] < splits[j], i is smaller,
                 else if splits[i] > splits[j], i is larger,
                 else they're equal

So, for example, compare(0, 1) should return i > j because 4.2 > 3.9.

Following is some C code that illustrates the solution using fairly little code. It relies on the qsort_r() C standard library function, which is a version of quicksort, but you could use any sorting algorithm. An important implementation detail is that the qsort_r() routine lets us pass an extra parameter that's provided to the comparison function; this lets us pass the splits array to the comparison function.

void sortSplits(float splits[], int index[], int count)
{
    // initialize the index array
    for (int i = 0; i < count; i++) {
        index[i] = i;
    }

    qsort_r(index, count, sizeof(int), splits, compareSplits);
}

int compareSplits(void *thunk, const void *item1, const void *item2)
{
    float *splits = (float*)thunk;
    int i = *(int*)item1;
    int j = *(int*)item2;

    if (splits[i] < splits[j])
        return -1; // less than
    else if (splits[i] > splits[j])
        return 1;  // greater than
    else
        return 0;  // equal
}

To use this code, call sortSplits() passing in the array of split times, an array of ints that's at least as long as the array of times, and the number of times. On return, the index array will contain the sorted list of indexes. In other words, if the resulting array looks like:

{3, 0, 1, 2}

it means that the split time at index 3 is the smallest, followed by the time at index 0, followed by the time at index 1, followed by the time at index 2.

The indexes here really work like pointers. You could even say that they ARE pointers in a sense. Indeed, you could implement exactly the same algorithm described above using an array of pointers in place of the array of indexes That would eliminate the need for passing the splits array as a separate parameter.

Answer 2

If you are not sorting the list, you are going to need to iterate over it once (minus 1 element) to determine all of the values rankings.

Or, try maintaining a separate array that sorts on insert, then reference the value (rank) of that key (value or time) when printing your data.

Answer 3

I'd do something like this:

• Create a data structure containing a time value and an integer value.
• Iterate over your original array, and create a second array of the data structures. The second (integer) value would be the index of each time in the original array.
• Sort the second array by time.
• The position of each time in the sorted array is the rank. You can apply ranks back to the original array by using the index value.

Answer 4

To determine the ranking you'll need to sort the array in a temporary sorted array. Easiest way I can think of is to create a data structure that contains both the time and the ranking, e.g. Javascript style:

var data = {
    time: 4.66,
    rank: 1
}

So first start building up your list with the raw data converted to rankable data objects:

var times = [];
var tempTimes = [];
var i;
// create from input arr objects and put to times and tempTimes
for (i = 0; i < arr.length(); ++i) {
    var obj = {
      time: arr[i]
    };
    times[i] = obj;
    tempTimes[i] = obj;
}

// sort tempTimes by time, using jQuery
tempTimes.sortElements(function(a, b) {
    return a.time > b.time ? 1 : -1; 
});
// iterate and add ranks to the objects
// since they are now ordered by time
for (i = 0; i < tempTimes.length(); i++ ) {
    tempTimes[i].rank = i;
}

// since times and tempTimes have the same objects
// (by reference), they should all now be updated 
// with the ranks set so use the times array to print 
// out the array with the ranks, since that is still
// in correct original order
printTable(times);

This would be done a bit differently in other languages, by exploiting their idioms, but the basic step of creating a data structure that contains both time and rank still remains throughout all. The basic data flow would look like the following diagram:

list of raw data
   |
   | convert
   v
list of rankable data ---wait for ranks to be set---> output
   |                        ^
   | sort by times          |
   v                        |
list of rankable data       |
sorted by time              |
   |                        |
   | add rank to data       |
   v                        |
list of data ranked --------+
by time