How to sort 2 arrays while keeping them connected to same element? [duplicate]

Question

My program sorts alphabetically by last name and places the first name beside it, however I want it to also sort by first name as well. How would I go about this?

    // Before sort
    for (int i = 0; i < NUM_PEOPLE; i++) {
       cout << first_names[i] << "\t" << last_names[i] << endl;
    }

    string temp;

    for (int pass = 0; pass < NUM_PEOPLE - 1; pass++)
        for (int i = 0; i < NUM_PEOPLE - 1; i++)
            if (last_names[i] > last_names[i + 1]) {
            temp = last_names[i];
            last_names[i] = last_names[i + 1];
            last_names[i + 1] = temp;
            temp = first_names[i];
            first_names[i] = first_names[i + 1];
            first_names[i + 1] = temp;
        }

    cout << "After sort:" << endl;

    for (int i = 0; i < NUM_PEOPLE; i++)
        cout << last_names[i] << "\t" << first_names[i]<< endl;

Answer 1

If you have no choice but to have the data in separate arrays or containers, the better way to do these types of sorts is to use an additional array of index numbers, and sort the index numbers.

The reason why you would want to do things this way is that if you had more than 2 arrays, it becomes more difficult to write 3 lines of swapping code per array that needs to be swapped. It would be much easier to swap just one array, regardless of the number of arrays you may have to keep in sync.

Here is an example:

//...

// Create an array of indices, starting from 0.
int index[NUM_PEOPLE];
for (int i = 0; i < NUM_PEOPLE; ++i)
   index[i] = i;

int temp;

for (int pass = 0; pass < NUM_PEOPLE - 1; pass++)
{   
    for (int i = 0; i < NUM_PEOPLE - 1; i++)
    {
        if (last_names[index[i]] > last_names[index[i + 1]]) 
        {
            temp = index[i];
            index[i] = index[i + 1];
            index[i + 1] = temp;
        }
    }
}
cout << "After sort:" << endl;

for (int i = 0; i < NUM_PEOPLE; i++)
    cout << last_names[index[i]] << "\t" << first_names[index[i]]<< endl;

Note that there is only one item swapped, and that is the index array -- the first_name and last_name arrays are not changed whatsoever. Note that when accessing the arrays in a sorted manner (note the output at the end), we use the index array as the index into each individual array.

Here is a complete example.

---

Here is a solution using std::sort that uses the same technique explained above:

#include <iostream>
#include <string>
#include <algorithm>

const int NUM_PEOPLE = 5;

int main()
{
    std::string first_names[NUM_PEOPLE] = { "Joe", "Peter", "Andy", "Anny", "Drake" };
    std::string last_names[NUM_PEOPLE] = { "Johnson", "Parker", "Sanchez", "Nguyen", "Bell" };

    // Before sort
    std::cout << "\nBefore sort:\n" << std::endl;
    for (int i = 0; i < NUM_PEOPLE; i++) {
        std::cout << first_names[i] << "\t" << last_names[i] << std::endl;
    }
    int index[NUM_PEOPLE];
    for (int i = 0; i < NUM_PEOPLE; ++i)
        index[i] = i;

    std::sort(index, index + NUM_PEOPLE, [&](int n1, int n2) 
    { return last_names[index[n1]] < last_names[index[n2]]; });

    std::cout << "\nAfter sort:\n" << std::endl;

    for (int i = 0; i < NUM_PEOPLE; i++)
        std::cout << last_names[index[i]] << "\t" << first_names[index[i]] << std::endl;
}

Output:

Before sort:

Joe Johnson
Peter   Parker
Andy    Sanchez
Anny    Nguyen
Drake   Bell

After sort:

Bell    Drake
Johnson Joe
Parker  Peter
Nguyen  Anny
Sanchez Andy

Answer 2

Seems like none of the other answers so far are sorting by first name. If you're alright with using STL containers and the std::sort algorithm, consider storing a vector of firstName, lastName pairs and providing your custom comparison function to consider the first and last name:

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

int main()
{
    vector< pair<string, string> > names;
    string firstName, lastName;
    while( cin >> firstName >> lastName ) {
        names.emplace_back(firstName, lastName);
    }
    sort( names.begin(), names.end(), [](auto const& a, auto const& b) {
        if( a.second < b.second ) return true;
        if( a.second == b.second ) return a.first < b.first;
        return false;
    } );
    for( auto const& name : names ) {
        cout << name.first << " " << name.second << "\n";
    }
    return 0;
}