Implementing a Sort that returns the index positions

[Larz]

Hey guys,

I've made a function that returns the index positions of the highest to lowest values within a array.

Essentially rather than sorting the array, it gives the positions of the sorted elements

e.g array {4,12,434,6,24)

it will return {2,4,1,3,0}, meaning the highest number in in position 2 then next highest is in pos 4 etc.

I couldn't find anything that could do this in the <algorithm> library so i made my own.

  int * order_high(const int * input_array, unsigned int size){
	int * temp, *output_array; 
	bool * value_used;
	unsigned int j;

	value_used = new bool[size];

	//initialize bool array
	for(unsigned int i = 0; i < size; ++i)
		value_used[i] = false;

	temp = new int[size];
	output_array = new int[size];

	for(unsigned int i =0; i < size; ++i)   // copy array to temp
		temp[i] = input_array[i];

	sort(temp,temp+size);

	for(unsigned int i = size; i != 0; --i){    // go down the sorted array from highest (sorted) value to lowest (sorted) value
		for(j = size-1; temp[i-1] != input_array[j] || value_used[j] == true; --j)  // find matching position in the input array & make sure we havent already included it
			;
		value_used[j] = true;
		output_array[(size-1) - (i-1)] = j; // put that position into the output array
	}
	return output_array;
}

My question is there a better way of doing this? My way is very hackish, and seems needlessly complicated for what im doing.

[JLBorges]

Do an indirect sort (of indices into the array):

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

int main()
{
    const int a[] = { 4, 12, 434, 6, 24 } ;
    for( int v : a ) std::cout << v << ' ' ;
    std::cout << '\n' ;

    std::size_t indices[ sizeof(a) / sizeof(a[0]) ] ;
    std::iota( std::begin(indices), std::end(indices), 0 ) ; // fill with 0, 1, ..., n-1

    // indirect (descending) sort on indices
    std::sort( std::begin(indices), std::end(indices),
                [&a] ( std::size_t i, std::size_t j ) { return a[i] > a[j] ; } ) ;

    for( std::size_t pos : indices ) std::cout << pos << ' ' ;
    std::cout << '\n' ;

}

http://coliru.stacked-crooked.com/a/24046a91f3429266

[Larz]

Thanks,

Knew that there had to be a better way.

+1 for forcing me to look up what a colon does inside a for loop

Never seen that before.

[Larz]

For those that stumble on to this after, here is JLBorges' answer in a function version and dealing with dynamic size arrays:

size_t * order_indices(const int * input_array, size_t size){
	size_t * indices;

    indices = new size_t[size];

    iota( indices, indices + size, 0 ) ; // fill with 0, 1, ..., n-1

    // indirect (descending) sort on indices
    sort( indices, indices + size,
                [input_array] ( size_t i, size_t j ) { return input_array[i] > input_array[j] ; } ) ;

   return indices;

}

[JLBorges]

If I were to write it, it would look something like this:

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

template < typename RANDOM_ACCESS_CONTAINER >
std::vector<std::size_t> order_indices_descending( const RANDOM_ACCESS_CONTAINER& seq )
{
    std::vector<std::size_t> indices( seq.size() ) ;
    std::iota( std::begin(indices), std::end(indices), 0 ) ; // fill with 0, 1, ..., n-1

    // indirect (descending) sort on indices
    std::sort( std::begin(indices), std::end(indices),
                [&seq] ( std::size_t i, std::size_t j ) { return seq[i] > seq[j] ; } ) ;

    return indices ;
}

int main()
{
    const std::vector<int> a { 4, 12, 434, 6, 24 } ;
    for( std::size_t pos : order_indices_descending(a) ) std::cout << pos << ' ' ;
    std::cout << '\n' ;
}

http://coliru.stacked-crooked.com/a/d8b19725341cbad1