-5

I have an array of arrays, for example: [[4, 204], [10, 39], [1, 500]]). I want to sort them by the first element of the subarray so that it becomes: [[1, 500], [4, 204], [10, 39]].

I couldn't find any answers to this question for C++.

How would I do this in C++?

code:

int n;
int time;  
int timeTable[100][2];

if (inputFile.is_open()) {

    for (int i = 0; i < 100; i++) {
        inputFile >> n;
        timeTable[i][0] = n;
        inputFile >> time;
        timeTable[i][1] = time;
    }

}
asdfjkdlf
  • 3
  • 4
  • 4
    You can't have such an array in C++. Show code! –  Sep 23 '17 at 17:19
  • Without code that show how you have defined your arrays, we cannot tell you how to sort them. We cannot be sure of you definition of array... – Phil1970 Sep 23 '17 at 17:45
  • sorry, I'm pretty new to c++. I'm not sure if how I declared the array is good/valid. I edited the question and put the code. – asdfjkdlf Sep 23 '17 at 17:55
  • *Is there a way to do this in C++* -- The answer is "yes". So what do you want us to do? – PaulMcKenzie Sep 23 '17 at 18:01
  • So here is the question to you -- are you willing to think outside the box? One way to sort the two dimensional array is to **not** sort the array, but 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. Please [see this as an example](http://coliru.stacked-crooked.com/a/f16a93233f111815) – PaulMcKenzie Sep 23 '17 at 18:13
  • @PaulMcKenzie ohh I see what you mean. Thanks for the help! – asdfjkdlf Sep 23 '17 at 18:21
  • I could post it as an answer, if this is indeed something worth considering. Didn't want to post as an answer and then be told "my teacher says I can't use this or that'. – PaulMcKenzie Sep 23 '17 at 18:23
  • @PaulMcKenzie yeah I'll definitely consider this. this isn't a school assignment it's just for practice – asdfjkdlf Sep 23 '17 at 18:26

1 Answers1

4

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 clumsy1 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] << "]\n";
}

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]).

1 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.

PaulMcKenzie
  • 34,698
  • 4
  • 24
  • 45