Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Sorting a vector in descending order within two ranges

Say I have a vector of integers:

std::vector<int> indices;
for (int i=0; i<15; i++) indices.push_back(i);

Then I sort it in descending order:

sort(indices.begin(), indices.end(), [](int first, int second) -> bool{return indices[first] > indices[second];})
for (int i=0; i<15; i++) printf("%i\n", indices[i]);

This produces the following:

14
13
12
11
10
9
8
7
6
5
4
3
2
1
0

Now I want to have the numbers 3, 4, 5, and 6 to be moved to the end, and keep the descending order for them (preferably without having to use sort for the second time). I.e., here is what I want:

14
13
12
11
10
9
8
7
2
1
0
6
5
4
3

How should I modify the comparison function of the std::sort to achieve that?

like image 288
Yury Avatar asked Feb 28 '20 13:02

Yury


People also ask

How do you order a vector in descending order?

Sorting a vector in descending order in C++ Sorting a vector in C++ can be done by using std::sort(). It is defined in<algorithm> header. To get a stable sort std::stable_sort is used. It is exactly like sort() but maintain the relative order of equal elements.

How do I sort a vector in descending order in R?

sort() function in R is used to sort a vector. By default, it sorts a vector in increasing order. To sort in descending order, add a “decreasing” parameter to the sort function.

How do you sort a vector in descending order in Matlab?

For example, if A is a matrix, then sort(A,2) sorts the elements of each row. B = sort(___, direction ) returns sorted elements of A in the order specified by direction using any of the previous syntaxes. 'ascend' indicates ascending order (the default) and 'descend' indicates descending order.


2 Answers

Your comparison function is wrong since the values you get as first and second are the elements of the std::vector. Therefore, there is no need to use them as indices. So, you need to change

return indices[first] > indices[second];

to

return first > second;

Now, regarding the problem you try to solve...

You can leave 3, 4, 5 and 6 out of comparison with other elements and still compare it with each other:

std::sort(
    indices.begin(), indices.end(),
    [](int first, int second) -> bool {
        bool first_special = first >= 3 && first <= 6;
        bool second_special = second >= 3 && second <= 6;
        if (first_special != second_special)
            return second_special;
        else
            return first > second;
    }
);

Demo

like image 63
NutCracker Avatar answered Oct 20 '22 15:10

NutCracker


Functions from the standard algorithms library like iota, sort, find, rotate and copy would make your life easier. Your example comes down to:

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <iterator>


int main()
{
  std::vector<int> indices(15);
  std::iota(indices.begin(), indices.end(), 0);
  std::sort(indices.begin(), indices.end(), std::greater<>());

  auto a = std::find(indices.begin(), indices.end(), 6);
  auto b = std::find(indices.begin(), indices.end(), 3);
  std::rotate(a, b + 1, indices.end());

  std::copy(indices.begin(), indices.end(), std::ostream_iterator<int>(std::cout, "\n"));
  return 0;
}

Output:

14
13
12
11
10
9
8
7
2
1
0
6
5
4
3


@TedLyngmo in the comments makes the good point that it could/should be improved with:
auto a = std::lower_bound(indices.begin(), indices.end(), 6, std::greater<int>{});
auto b = a + 4;
like image 5
acraig5075 Avatar answered Oct 20 '22 16:10

acraig5075