Sort vector of vector

Question

I have a vector of vectors of int like this:

std::vector<std::vector<int>> vec_vec{{3,5,1,6},{2,4},...};

The results should be

 Case1:   {{1, 2, 3, 4}, {5, 6}} 
 Case2:  {1,2,3,4,5,6}
 Case3:  {{1, 3, 5, 6}, {2, 4}}

I found many ways to do this, the best one I found need complexity O(n^2) to sort them.

What's the best complexity for the case1, case2 and case3?

So what's the best way to write a native (c++11,c++14) cross platform code to sort that's vector? is O(n^2) is the best complexity? The memory is important also.

I checked this solution here, but it seems it also took O(n^2) to sort the vectors?

Do you suppose that result should be `{{1, 2, 3, 4}, {5, 6}}`? — Alex, Nov 25 '15 at 15:29
If I understand, you want to **merge** your vectors first and then to sort the merged one, right? Merge without repetitions? — Paolo M, Nov 25 '15 at 15:32
Could you do by insertion? loop over the vector and insert in new vector in their order... — jabujavi, Nov 25 '15 at 16:11
What is `n`? Is it the number of vectors or the total number of values in all the vectors? — JeremyP, Nov 25 '15 at 16:30
What's your O(n^2) solution? The builtin sort function is O(nlogn) in the average case. For the third case you don't even need to do anything except sort. — interjay, Nov 25 '15 at 16:32
In case 2 first you merge them and then you sort them. In case 3 you sort them individually, without sorting. But in case 1? Do you merge them, sort, and then split them again based on the number of elements in the original vectors? — Fabio says Reinstate Monica, Nov 25 '15 at 16:32

score 0 · Answer 1 · answered Nov 25 '15 at 17:16

The easiest case is case 2. To solve that, make a temporary new vector, move all elements there, and sort the new vector.

std::vector<int> temp;
for (const auto& vec: vec_vec)
{
    std::copy(vec.begin(), vec.end(), std::back_inserter(temp));
}
std::sort(temp.begin(), temp.end());

The copying part is O(n); the sorting part is O(n log(n)).

To implement case 1, copy the elements from temp back to vec_vec - this should be easy.

Sort vector of vector

1 Answers1