sort array by first item in subarray c++

Question

Closed. This question needs details or clarity. It is not currently accepting answers.

Answer 1

One way to sort the array is to not sort the array itself.

Instead, sort an array of indices that point inside of the array, and then use the sorted index to access the elements. It is much easier to do that than to manipulate a 2d array in a sorting function.

In general, if you have the memory for the array of indices (we will need additional storage for the index array), sorting objects that have

1. a large payload per item, or
2. the original order of the array needs to be kept around, or
3. sorting is just clumsy¹ or impossible to manipulate easily in a sorting algorithm,

can use this technique that will be described here.

Here is an example:

#include <algorithm>
#include <iostream>

int main()
{
    int index[3] = {0,1,2};
    int timeTable[3][2] = {{4, 204}, {10, 39}, {1, 500}};
    std::sort(index, index + 3, [&](int n1, int n2){ return timeTable[n1][0] < timeTable[n2][0]; });
    for (int i = 0; i < 3; ++i)
       std::cout << "The index is " << index[i] << ".  The data at this index is  [" << 
                 timeTable[index[i]][0] << " " << timeTable[index[i]][1] << "]
";
}

Live Example

So basically we create an initial index array numbered from 0 to n-1 where n are the number of items to sort. Then we call std::sort on the index, and in the sorting criteria, we compare the items in the actual array using the indices passed to the sorting predicate. The result will be the index array having its elements swapped around during the sort instead of the original array's elements being swapped.

Note that the sorting predicate is very simple -- we state exactly what we want the indices to represent in the sort by using the indices being passed on the timeTable array. There is no tricky, error-prone, or code that does not scale well if one of the items is out of order (for example, the parallel array scenario -- imagine 20 arrays and having to swap 20 items just because one item is out of order).

After sorting the indices, when it comes time to use the timeTable array, we use the index array to point to the items (note how we specify the index by using timeTable[index[i]][0] instead of timeTable[i][0]).

---

¹ Included in the "clumsy" category are those "parallel array sort" questions that show up on StackOverflow, where the poster is asked to sort multiple arrays "in parallel" based on data in one of those arrays.