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.