Sorting Of two arrays

Question

Suppose I have been given two array.For ex- Process With their Arrival Time and Finish Time. I want to sort it on the basis of finish time.On the basis of Finish Time,Arrival Time Should also be sorted. I can use bubble sort or selection sort for this purpose. But Is there any STL for this purpose? Can I use sort() function with some modifications?

You'll want to use a stable sort routine: http://en.wikipedia.org/wiki/Sorting_algorithm#Stability. Also, show some code or at least pseudo-code. — Drakes, May 25 '15 at 05:44
possible duplicate. http://stackoverflow.com/questions/3909272/sorting-two-corresponding-arrays. — Achilles Rasquinha, May 25 '15 at 05:50

score 0 · Accepted Answer · edited May 23 '17 at 11:43

One way to do it would be to create a vector of (end, start) pairs (in this order - explanation below), sort it, then split the pairs of the sorted output:

#include <utility> // For pair
#include <algorithm> // For sort

std::vector<std::pair<size_t, size_t>> intervals;
for(size_t i = 0; i < start.size(); ++i)
    intervals.push_back(std::make_pair(end[i], start[i]));

std::sort(std::begin(intervals), std::end(intervals)); // (*)

start.clear();
end.clear();
for(size_t i = 0; i < start.size(); ++i)
{
    end[i] = intervals[i].first;
    start[i] = intervals[i].second;
}

Note the line with the (*) comment. STL pairs' order is lexicographic, which we exploit here (sorting pairs will sort by the firsts for free).

score 0 · Answer 2 · answered May 25 '15 at 07:33

You can pass a functor to std::sort or provide operator < for your data:

struct MyClass
{
    std::size_t arrivalTime;
    std::size_t finishTime;
};

std::vector<MyClass> myClasses = //..
std::sort(myClasses .begin(), myClasses.end(),
          [](const MyClass& lhs, const MyClass& rhs) {
              return std::tie(lhs.finishTime, lhs.arrivalTime)
                     < std::tie(rhs.finishTime, rhs.arrivalTime);
         });

or simply

bool operator< (const MyClass& lhs, const MyClass& rhs)
{
    return std::tie(lhs.finishTime, lhs.arrivalTime)
           < std::tie(rhs.finishTime, rhs.arrivalTime);
}

and later:

std::sort(myClasses .begin(), myClasses.end());

Sorting Of two arrays

2 Answers2