0

I have a set of n- dimension point store in vector< vector<double> > 

ex A[0][1].............[N], and A[0][0] = X, A[0][1] = Y, A[0][2] = Z

and I want to sort the vector of all of the dimension

ex sort X, Y, Z ,.........N in ascending order


ex              A[0] = (1,5,3), A[1] = (3,2,1) A[2] = (2,8,4) after sorting
index:            0               1             2
                A[0] = (1,5,3), A[1] = (2,8,4) A[2] = (3,2,1)
original index :  0               2             1

I find that sort(vector.begin(), vector.end()) can sort it but how can I record the original index with a additional vector?

Is there a algorithm or C++ feature can solve it?

Thx in advance.

Jason
  • 1,573
  • 3
  • 18
  • 46
  • http://stackoverflow.com/questions/1577475/c-sorting-and-keeping-track-of-indexes –  May 04 '13 at 15:32
  • if memory is not a problem. take your n-dimensional vector and convert it to 1-D vector, and then call sort on the new vector. – Bill May 04 '13 at 15:34
  • sorry, that I cannot change its dimension because I need that to do some following steps. – Jason May 04 '13 at 15:36
  • BTW, do you only want to sort A[0] ? – Bill May 04 '13 at 15:37
  • The above seem to work in 1D. – Jason May 04 '13 at 15:38
  • I want to sort at least A[0], and should keep the original index. – Jason May 04 '13 at 15:39
  • what do you mean by keep the original index? – Bill May 04 '13 at 15:39
  • I add it in the question. – Jason May 04 '13 at 15:42
  • put your second vector inside a `struct`/`class` which also contains an `int`, populate these `int`s before the sort with the current index and they will tell you the original order after the sort. You can also define the `<` operator on the `struct`. – Dave May 04 '13 at 15:49
  • It is not clear from your question, how you want the first dimensaion of `A` to be sorted. You can use `std::sort(A[i].begin(), A[i].end())` to sort each `A[i]`s individually. – Bill May 04 '13 at 15:49
  • I just have to know each element's original index and ecah element should be sort by X and whether other dimension in the elemnt is sorted or not is don't care. – Jason May 04 '13 at 15:59
  • @Dave Would you mind putting that as an answer? That solves OP's question, IMO. – UltraInstinct May 04 '13 at 16:16

1 Answers1

1

You need to somehow keep the information about the index. I can see two ways of doing this :

1-Since you represent your point by a vector, you can had another dimension that will represent the orginal index :

//Adding index info, inportant that your index be the last dimension , otherwise the sort is incorrect for(auto point = vector.begin(),unsigned int index=0;point != vector.end(); ++point,++index){ point->push_back(index) };

Then sort the same way you are doing now :

sort(vector.begin(), vector.end())

and you access the original index with A[0][n]

The cool thing about that is that it allow you to keep track of the index in a very convenient way, but you need to be able to modify the representation of your point.

2- The other way is to have an external table of indices and sort that using custom comp. operator :

you start by creating a vector of indices

std::vector indices(vector.size());

for(unsigned int index =0;index != indicies.size(); ++point){ indicies[index] = index ; };

//and sort...

std::sort(indices.begin(),indices.end(),[&](unsigned int i,unsigned int j) { return vector[i] < vector[j]})

now you need an additional level of indirection to go trough your points in the sorted order : A[indices[0]],A[indices[1]],... So the original position of A[indices[x]] is simply x

The main to remember between those two ways of doing it is that in the first you move your data around and not in the second , depending on what you are doing on your points, one might be better that the order

GreyGeek
  • 918
  • 5
  • 14
  • Thank you, the first one is cool! And can I ask the second's method is? I cannot understand it. – Jason May 04 '13 at 16:31
  • Is there a way to not modify the point, because I have to calculate the closest distance. – Jason May 04 '13 at 17:03