How to sort multiple arrays based on one and print them out

Question

I used a string-stream to read an input file with 10 lines and stored all the values into separate arrays. ID, first, last, city, state, and GPA. It looked like this.

1 Nathan Humphery Kansas MO 3.35
2 Sara Jonathan LeesSummit MO 3.56
3 Kayla James Liberty KS 3.78
4 Kyle Davis Independence KS 2.98
...
8 Daniel Earla Independence KS 3.77

So the ID array would be { 1, 2, 3, 4, ..., 8}
and the city array would be {Kansas, LeesSummit, Liberty, Independence, ..., Independence}

One of the functions in my program is supposed to print out the information sorted by city.

I used the selection sort algorithm to sort the city array to put them in the correct alphabetical order. But now I'm not sure how to properly sort the other arrays to match the information that was in the city array. Can something be added to the SelectionSort function that would match the changes that happened in the city array to the other arrays? Do I even need to sort every array, or is there an easier way that I'm just missing?

I can't use things such as "#include algorithm" and "sort()" yet, and I'm also using namespace std.

void SelectionSort(string city[], int size) 
{
    int i;
    int j;
    int indexSmallest;
    string temp;

    for (i = 0; i < size; ++i)
    {

        indexSmallest = i;
        for (j = i + 1; j < size; ++j)
        {

            if (city[j] < city[indexSmallest])
            {
                indexSmallest = j;
            }
        }

        temp = city[i];

        city[i] = city[indexSmallest];

        city[indexSmallest] = temp;
    }
}

The output should look something like this.

4 Kyle Davis Independence KS 2.98
8 Daniel Earla Independence KS 3.77
1 Nathan Humphery Kansas MO 3.35
2 Sara Jonathan LeesSummit MO 3.56
3 Kayla James Liberty KS 3.78

Although it's possible to implement array sorting this way, this is to way too complicated. Instead, it's much simpler to have a single array of structures, and sort just one array. There's no reason to go through all the effort to do this correctly, when a much simpler solution exists. — Sam Varshavchik, Sep 22 '19 at 16:06
The trick in sorting parallel arrays is *not* to sort the array itself. Instead, you sort an array of indices, and when referencing the array, you use the index array. — PaulMcKenzie, Sep 22 '19 at 16:27

PilouPili · Answer 1 · 2019-09-22T16:33:02.287

If you are storing arrays, maybe try doing it with std::vector or std::list that will able you to use the ordering function next.

I would use a function to get the classification for one of your arrays (in your example the cities). something like

template<class _Array> void get_ordered_index(const _Array& arr, std::vector<size_t>& mapped)
{
    mapped.resize(arr.size());
    std::map<_Array::value_type, size_t> ordering_map;
    size_t i = 0;
    for (i = 0; i < arr.size(); i++)
    {
        ordering_map[arr[i]] = i;
    }
    i = 0;
    for (auto&& item : ordering_map)
    {
        mapped[i] = item.second;
        i++;
    }
}

You get the ordering with :

std::<vector> order;
get_ordered_index(city, order)

then to print

for (size_t i = 0; i < order.size(); i++)
{
    std::cout << city[order[i]]/*whatever is next*/<<std::endl;
}

Full working example :

int main()
{
    std::vector<std::string> city{"Kansas","LeesSummit", "Liberty","Independence"  };
    std::vector<std::string> names{ "Humphery","Jonathan", "James","Davis" };
    std::vector<size_t> order;
    get_ordered_index(city, order);
    size_t j;
    for (size_t i = 0; i < order.size(); i++)
    {
        j = order[i];
        std::cout << city[j]<<' '<< names[j] <<std::endl;
    }
}

ouputs:

Independence Davis
Kansas Humphery
LeesSummit Jonathan
Liberty James

score 0 · Accepted Answer · answered Sep 22 '19 at 16:41

Using the techniques used in this answer, you can create an array of indices, and sort the index array based on the criteria you're interested in. Then when referencing the data in a sorted manner, you use the index array.

#include <vector>
//...
std::vector<int> index_array;
int main()
{
    for (int i = 0; i < number_of_items; ++i)
        index_array.push_back(i);
//...
    SelectionSort(city, size)
}

void SelectionSort(string city[], int size) 
{
    int i;
    int j;
    int indexSmallest;
    string temp;

    for (i = 0; i < size; ++i)
    {
        indexSmallest = i;
        for (j = i + 1; j < size; ++j)
        {
            if (city[index_array[j]] < city[index_array[indexSmallest]])
            {
                indexSmallest = j;
            }
        }

        temp = index_array[i];
        index_array[i] = index_array[indexSmallest];
        index_array[indexSmallest] = temp;
    }
}

Then when accessing the arrays, use the array of indices:

for (int i = 0; i < size; ++i)
   std::cout << city[index_array[i]] << "\n" << names[index_array[i]] << "\n\n";

How to sort multiple arrays based on one and print them out

2 Answers2

Linked