Creating a vector of indices of a sorted vector

Question

Variable x is a vector of n ints, and I want to sort the vector in ascending order. However, for reasons outside the scope of this question, I want to vector to remain untouched. Therefore, rather than actually sorting the contents of x, I want to create another vector of n indices, where each index refers to the respective value in x, if x were to have been sorted.

For example:

std::vector<int> x = {15, 3, 0, 20};
std::vector<int> y;
// Put the sorted indices of x into the vector y
for (int i = 0; i < 4; i++)
{
    std::cout << y[i];
}

Should give the output:

Corresponding to values in x:

I can think of plenty of timely ways of implementing this, but I'm wondering whether the STL has something build-in to perform this efficiently for me?

I think you can use `std:sort` by providing your own Comparator which does the dereferencing into the target `std::vector`.. — Galik, Sep 18 '14 at 20:29
See http://stackoverflow.com/questions/1577475/c-sorting-and-keeping-track-of-indexes — sfjac, Sep 18 '14 at 20:42

quantdev · Accepted Answer · 2014-09-18T20:48:20.220

26

1) Create y as a vector of index (an integer range)

2) Sort this range with a comparator that returns the indexes elements from x Using the Standard Library, that gives :

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

int main() {

    std::vector<int> x = {15, 3, 0, 20};

    std::vector<int> y;

    std::vector<int> y(x.size());
    std::size_t n(0);
    std::generate(std::begin(y), std::end(y), [&]{ return n++; });

    std::sort(  std::begin(y), 
                std::end(y),
                [&](int i1, int i2) { return x[i1] < x[i2]; } );

    for (auto v : y)
        std::cout << v << ' ';

    return 0;
}

Live demo.

edited Sep 18 '14 at 20:48

answered Sep 18 '14 at 20:38

quantdev

23,517
5
55
88

1

Thanks for the link to the live demo -- did not know about that website! – Karnivaurus Sep 18 '14 at 20:43
1

Nice examples of lambdas too. – Mark Ransom Sep 18 '14 at 20:48
not correct if you change array to {15, 3, 0, 20, 2, 77} for example – sh1ng Jul 29 '16 at 23:23
@sh1ng I see the correct output, see [here](http://coliru.stacked-crooked.com/a/b393afce4826df1b) : what error do you see ? – quantdev Aug 01 '16 at 00:57
1

Amazing trick! You sort the indices array with a comparator that looks at the values array :) – SomethingSomething Jul 05 '17 at 14:00

Chris Drew · Answer 2 · 2014-09-20T10:52:59.653

14

Fill y with all the indices of x then use std::sort on y but provide a comparator that compares the corresponding elements in x:

  std::vector<int> y(x.size());
  std::iota(y.begin(), y.end(), 0);
  auto comparator = [&x](int a, int b){ return x[a] < x[b]; };
  std::sort(y.begin(), y.end(), comparator);

edited Sep 20 '14 at 10:52

answered Sep 18 '14 at 20:30

Chris Drew

14,926
3
34
54

score 4 · Answer 3 · answered Sep 18 '14 at 20:44

You can provide your own Comparator that checks the target vector's values while sorting a vector of indexes rather like this:

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

struct IdxCompare
{
    const std::vector<int>& target;

    IdxCompare(const std::vector<int>& target): target(target) {}

    bool operator()(int a, int b) const { return target[a] < target[b]; }
};

int main()
{
    std::vector<int> x = {15, 3, 0, 20};
    std::vector<int> y;

    // initialize indexes
    for(size_t i = 0; i < x.size(); ++i)
        y.push_back(i);

    std::sort(y.begin(), y.end(), IdxCompare(x));

    std::cout << "\nvector x: " << '\n';
    for(size_t i = 0; i < x.size(); ++i)
        std::cout << x[i] << '\n';

    std::cout << "\nvector y: " << '\n';
    for(size_t i = 0; i < x.size(); ++i)
        std::cout << y[i] << '\n';

    std::cout << "\nvector x through y: " << '\n';
    for(size_t i = 0; i < x.size(); ++i)
        std::cout << x[y[i]] << '\n';
}

OUTPUT:

vector x: 
15
3
0
20

vector y: 
2
1
0
3

vector x through y: 
0
3
15
20

score 1 · Answer 4 · answered Sep 18 '14 at 20:51

We can take a "refers" approach directly and use an array of pointers to values in the source vector.

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

int main(int argc, const char * argv[]) {
    //a source vector, who's order shouldn't be changed
    std::vector<int> values = {15, 4, 20, 25, 0, 19, -5};
    //a vector of pointers to the values in the source vector
    std::vector<int *> pointersToValues;
    pointersToValues.reserve(values.size());

    for(auto& value : values){
        pointersToValues.push_back(&value);
    }

    //two comparators in form of lambda functions
    auto descendingOrderSorter = [](int * i, int * j){
        return *i > *j;
    };

    auto ascendingOrderSorter = [](int * i, int * j){
        return *i < *j;
    };

    //examples of usage
    std::cout<<"Sorting in a descending order"<<std::endl;
    std::sort( pointersToValues.begin(), pointersToValues.end(), descendingOrderSorter);
    for(int i = 0; i < pointersToValues.size(); ++i) {
        std::cout << "index: " << i << ", value: " << *pointersToValues[i] << std::endl;
    }

    std::cout<<"Sorting in an ascending order"<<std::endl;
    std::sort( pointersToValues.begin(), pointersToValues.end(), ascendingOrderSorter);
    for(int i = 0; i < pointersToValues.size(); ++i) {
        std::cout << "index: " << i << ", value: " << *pointersToValues[i] << std::endl;
    }

    return 0;
}

pointersToValues[i] would give you a pointer to the original value, *pointersToValues[i] would give you the value.

score 0 · Answer 5 · answered Sep 18 '14 at 20:33

You can do a sort into another list then a comparison with the unsorted list then a 3rd list where you can store the indices i.e nlog(n) + n^2 or just O(n^2)

Note: this is Pseudo code

vector<int> x = {15, 3, 0, 20};
vector<int> y = sort(x);
vector<in> z;
for(int i = 0; y < y.size(); i++){
   for(int j = 0; j < y.size(); j++){
      if(y[i] == x[j]){
         z.push_back(j);
      }
   }
}

Creating a vector of indices of a sorted vector

5 Answers5

Linked