Sorting two corresponding arrays

Question

I have this code here that has two arrays. It sorts arr[], so that the highest value will be in index 0. Now the second array arr1[] contains strings, I'd like the code to apply whatever changes where made to arr[] to arr1[]. So that arr[0] would return 6, while arr1[0] would return the string "d1". Notice how "d1" was at the same index as 6? After sorting I'd like the same values to still have their string counterparts.

How would I go about doing this?

#include <iostream>
#include <iomanip>
#include <algorithm>
#include <functional>
using namespace std ;


main(){
int arr[ 5 ] = { 4, 1, 3, 6, 2 };

string arr1[ 5 ] = { "a1", "b1", "c1", "d1", "e1" };

std::sort( arr, arr + 5, std::greater< int >() );
cout << arr[0] << arr1[0] << endl;

system("pause");
}

Answer 1

You need to combine them together and then sort the combined pair and then un-combine the pairs.

int arr[ 5 ] = { ... };
string arr1[ 5 ] = { ... };
pair<int, string> pairs[ 5 ];

for ( int i = 0; i < 5; ++i )
  pairs[ i ] = make_pair( arr[ i ], arr1[ i ] );

sort( pairs.begin(), pairs.end() );

for ( int i = 0; i < 5; ++i )
{
  arr[ i ] = pairs[ i ].first;
  arr1[ i ] = pairs[ i ].second;
}

Really though, if arr and arr1 are related then they should be stored as the pair (or at least a custom struct) anyway. That way you don't need to use this as an intermediate step.

Answer 2

Rather than sort the arrays, sort the indices. I.e., you have

int arr[5]={4,1,3,6,2}
string arr1[5]={"a1","b1","c1","d1","e1"};

and you make

int indices[5]={0,1,2,3,4};

now you make a sort indices comparitor that looks like this (just and idea, you'll probably have to fix it a little)

class sort_indices
{
   private:
     int* mparr;
   public:
     sort_indices(int* parr) : mparr(parr) {}
     bool operator()(int i, int j) { return mparr[i]<mparr[j]; }
}

now you can use the stl sort

std::sort(indices, indicies+5, sort_indices(arr));

when you're done, the indices array will be such that arr[indices[0]] is the first element. and likewise arr1[indices[0]] is the corresponding pair.

this is also a very useful trick when you're trying to sort a large data object, you don't need to move the data around at every swap, just the indices.