Sort and keep track of elements

Question

Just to know, I'm talking C++ now.

Suppose I have an array A = {4, 1, 5, 2, 3} and sort it in A_sorted = {1, 2, 3, 4, 5}. I would like to keep the following information: where is now element e (from array A) in the sorted array A_sorted? e.g.: element with index 2 in A (5) has now index 4 in A_sorted.

The question is more like: can one use STL to achieve this?

Answer 1

There's no off-the-shelf functionality to achieve this, but there are work-arounds. You can, for example, keep an array of user-defined structs that also contain the original position:

A = { {4,0}, {1,1}, {5,2}, {2,3}, {3,4}}

And then sort this using a custom comparator function that sorts by the value and not the original index.

A_sorted = {{1,1}, {2,3}, {3,4}, {4,0}, {5,2}}

Answer 2

Try this out: If you want to convert to vector:

 int A[] = {4, 1, 5, 2, 3};
 int A_sorted [] = {1, 2, 3, 4, 5};
 std::vector<int> v(A_sorted, A_sorted + 5);  

  for (int i=0; i<5; i++)
  {          
    std::vector<int>::iterator low = lower_bound (v.begin(), v.end(), A[i]);   
    std::cout << "Element: " << A[i] << " is at: " << distance(v.begin(), low)  << std::endl;
  }

If you want to work on raw array:

 int A[] = {4, 1, 5, 2, 3};
 int A_sorted [] = {1, 2, 3, 4, 5};

  for (int i=0; i<5; i++)
  {      
    int* low = std::lower_bound (&A_sorted[0], &A_sorted[5], A[i]);   
    cout << "Element: " << A[i] << " is at: " << distance(&A_sorted[0], low)  << endl;
  }