Index Sorting using stl

I have a vector of floats which i wish to sort.
I dont want to perform in place sorting but want to store the indices of the elements in sorted order in another vector.
Is there any way to do this using STL (as i want to be efficient my code needs to sort anout 1000 entries)

for eg.
let my vector be (1.0,4.1,3.1,2.3)
then i want the output vector to be
( 1,4,3,2) // indices of original vector in sorted order


you can construct another vector which contains the unsorted vector values using the copy constructor, you can then sort the values in the second vector using std::sort from algorithm

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
	
	std::vector<float> fValue( 5 );
	fValue[ 0 ] = 344.2;
	fValue[ 1 ] = 34.5;
	fValue[ 2 ] = 0.1;
	fValue[ 3 ] = 1e+24;
	fValue[ 4 ] = 12;
	
	std::cout << "Value of unsorted floats: ";
	for( auto i : fValue )
		std::cout << i << " ";
		
	std::vector<float> fValue2( fValue );
	std::sort( fValue2.begin(), fValue2.end() );
	
	std::cout << "\nValue after sort: ";
	for( auto i : fValue2 )
		std::cout << i << " ";
		
		
	return 0;
}


Value of unsorted floats: 344.2 34.5 0.1 1e+24 12 
Value after sort: 0.1 12 34.5 344.2 1e+24 

Last edited on
i though of that but in my program the index of the float(marks) correspond to the index in another vector of names(strings) and to the index in other vectors of marks.
Hence the only feasible way is to get a vector which has the indices in sorted order and then use those to ouptut a sorted list of marks with the coresponding names..
My Data structure

Namevec___ marksvec1_marksvec2_ marksvec3________Index
a____________10.5______13.5______ 23.5_____________0
b____________12.5______12.5______ 21.5_____________1
c____________10.5_______ 3.5______ 22.5_____________2

.
.
.
.

I hope you understand my problem now.
http://stackoverflow.com/questions/1577475/c-sorting-and-keeping-track-of-indexes

There are some posts here which i think could do my job. But i dont understand them (im a begginer) well enough to be able to modify to my needs.
Thanks for the Help!!
Last edited on
To sort indices into another container, your comparison must index the other container for the comparison.

1
2
3
4
5
6
7
8
9
10
template <typename Container>
struct compare_indirect_index
  {
  const Container& container;
  compare_indirect_index( const Container& container ): container( container ) { }
  bool operator () ( size_t lindex, size_t rindex ) const
    {
    return container[ lindex ] < container[ rindex ];
    }
  };

Now you can sort your indices by the indexed container:

1
2
3
4
5
6
  vector <double> numbers { 1.0, 4.1, 3.1, 2.3 };

  vector <size_t> indices( numbers.size(), 0 );
  iota( indices.begin(), indices.end(), 0 );  // found in <numeric>

  sort( indices.begin(), indices.end(), compare_indirect_index <decltype(numbers)> ( numbers ) );

Hope this helps.
The secret is to use currying to sneak the data into your compare function.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <numeric>      // std::iota
#include <algorithm>    // std::sort
#include <iostream>     // std::cout
#include <functional>   // std::bind
using namespace std::placeholders;

double data[10]={2.7182, 3.14159, 1.202, 1.618, 0.5772, 1.3035, 2.6854, 1.32471, 0.70258, 4.6692};
int index[10];

bool compare(int a, int b, double* data)
{
    return data[a]<data[b];
}

int main()
{
    std::iota(std::begin(index), std::end(index), 0); // fill index with {0,1,2,...} This only needs to happen once

    std::sort(std::begin(index), std::end(index), std::bind(compare,  _1, _2, data ));

    std::cout << "data:   "; for (int i=0; i<10; i++) std::cout << data[i] << " "; std::cout << "\n";
    std::cout << "index:  "; for (int i=0; i<10; i++) std::cout << index[i] << " "; std::cout << "\n";
    std::cout << "sorted: "; for (int i=0; i<10; i++) std::cout << data[index[i]] << " "; std::cout << "\n";

    std::cin.get();
    return 0;
}

Topic archived. No new replies allowed.