sorting algorithm returning indeces

[Michael02]

Hello,

I have some double values. For sorting them I could simply use std::sort(.). However, I actually don't need the sortet values but the indeces.

E.g. "sort({.7, .2, .9, 3.3, .3, .1, .6})" should give me
{5, 1, 4, 6, 0, 2, 3}.

I am not really sure if std::sort(.) already supports this functionality, but I am sure Im not the first one with this problem.


Does anyone have an idea?

Thanks a lot

[AbstractionAnon]

You're going to need to write your own algorithim as none of the standard algorithims provide only indexes. You can take any of the classic sort algorithims.
Create a copy of the source array since you don't want to modify that. Then as you're storing numbers in to the output array, store it's index into the index array.

[Michael02]

Thanks for the reply.
The original array can be modified as I am not interested in it any more. I only require the indexes. So the original array can be used and changed during computation.

[JLBorges]

> I am sure Im not the first one with this problem.

No, you are not. The kind of sort you are looking for is called an 'indirect sort'

#include <iostream>
#include <algorithm>

int main()
{
    constexpr std::size_t N = 7 ;
    const double values[N] = { 0.7, 0.2, 0.9, 3.3, 0.3, 0.1, 0.6 } ;

    std::size_t indices[N] ;
    std::iota( indices, indices+N, 0 ) ;

    // indirect sort of indices on corresponding values
    std::sort( indices, indices+N,
                [=]( std::size_t a, std::size_t b ) { return values[a] < values[b] ; } ) ;

    for( auto i : indices ) std::cout << i << ' ' ; // 5 1 4 6 0 2 3
    std::cout << '\n' ;
}