CODEWITHSUNDEEP
c++arrayssortingc++11structure
cryptomanic
cryptomanic

Reputation: 6316

sorting an array and maintaining element's old index

I have an array A:

A     =   [10 11 3 15 8 7]
index =    0   1 2  3 4 5

I want to sort this array.After sorting I want the information of old index.For this I can create a structure like this.

struct VnI{
  int value;
  int index;
};

sorting the array of structure with respect to value solve my problem.But I want to know that is it possible to solve this using sort or any other function in C++11.

I have tried this way:

struct VnI{
int V;
int I;
};

bool comparator(VnI x,VnI y){
    if(x.V < y.V)
        return true;
    return false;
}
int maximumGap(const vector<int> &A) {
   vector<VnI> B;
   for(int i = 0;i < A.size();i++){
      B[i].I = i;
      B[i].V = A[i];
}
sort(B.begin(),B.end(),comparator);
for(int i = 0;i < B.size();i++){
    cout<<B[i].I<<" "<<B[i].V<<endl;
  }
}

But I got runtime error. Please help.

Upvotes: 2

Views: 645

Answers (4)

6502
6502

Reputation: 114579

Normally what is done is the opposite... i.e. given an array x of elements compute an array of integers ix so that x[ix[i]] appears to be sorted under a certain criteria.

This allows representing the container with different orderings without actually having to move/copy the elements.

With C++11 this can easily be done using lambdas:

// Build the index vector ix
std::vector<int> ix(x.size());
for (int i=0,n=x.size(); i<n; i++) ix[i] = i;

// Sort ix according to the corresponding values in x
// (without touching x)
std::sort(ix.begin(), ix.end(),
          [&x](int a, int b) { return x[a] < x[b]; });

This ix index array is what you are asking for (i.e. the "old" position of an element: ix[i] is where the i-th element of the sorted list was in the original array) and there is no need to modify the input array.

Upvotes: 1

ggrr
ggrr

Reputation: 7867

do you pefer to use vector and pair?

each pair has "first" and "second", put "first"=value to sort,"second"=original index, create a pair for each element and put them into vector to sort:

int N[]={10,11,3,15,8,7};
std::vector<std::pair<int,int> > v;
//create pair for each element
for(int i=0;i<sizeof(N)/sizeof(int);i++){
    //first is value of array,second is original index
    v.push_back(std::make_pair(N[i],i));
}

//sort the vector of pair
sort(v.begin(),v.end());

//get original index from second of pair
for(std::pair<int,int>& p : v){
    std::cout << p.first << ":" << p.second << std::endl;
}

output

3:2
7:5
8:4
10:0
11:1
15:3

Upvotes: 2

Sarfaraz Nawaz
Sarfaraz Nawaz

Reputation: 361762

This code is wrong:

vector<VnI> B;  

for(int i = 0;i < A.size();i++){
   B[i].I = i;
   B[i].V = A[i];
}

When you write B[i], it assumes that B is at least of size i+1. Since the maximum value of i (which you used an index to B) is A.size()-1. The assumption in your code is that B is at least of size A.size(). This assumption is wrong — the fact is that B is of size 0.

Unfortunately operator[] of std::vector doesn't check for out of range index. If you use at(), the code will throw std::out_of_range exception:

vector<VnI> B;  

for(int i = 0;i < A.size();i++){
   B.at(i).I = i;
   B.at(i).V = A[i];
}

Now this would throw std::out_of_range exception.

Anyway, one simple fix could be this:

 vector<VnI> B (A.size());  //initialize B with the size of A.

 for(int i = 0;i < A.size();i++){
    B[i].I = i;
    B[i].V = A[i];
 }

However, I'd suggest this solution:

 vector<VnI> B;      
 B.reserve(A.size()); 

 for(int i = 0;i < A.size(); i++){
    B.emplace_back(i, A[i]);
 }

I'd also suggest you read more about std::vector, especially the following functions:

  • size()
  • capacity()
  • resize()
  • reserve()
  • push_back()
  • operator[]
  • at()
  • emplace_back()
  • and all the constructors.

Also, learn to naming your variables properly and be consistent with it.

Hope that helps.

Upvotes: 2

Kieren Pearson
Kieren Pearson

Reputation: 470

You are trying to sort a list of custom objects, answerd here:

SO Link

Once you list the list of VnI objects you can then access there old index's through the I member that I presume is the index.

Upvotes: -1

Related Questions