C sorting and keeping track of indexes

Question

Using C    and hopefully the standard library  I want to sort a sequence of samples in ascending order  but I also want to remember the original indexes of the new samples  For example  I have a set  or vector  or matrix of samples A    5  2  1  4  3   I want to sort these to be  B    1 2 3 4 5   but I also want to remember the original indexes of the values  so I can get another set which would be  C    2  1  4  3  0   - which corresponds to the index of each element in  B   in the original  A   For example  in Matlab you can do    a b  sort  5  8  7    a   5 7 8  b   1 3 2  Can anyone see a good way to do this

User · Answer

Are the items in the vector unique  If so  copy the vector  sort one of the copies with STL Sort then you can find which index each item had in the original vector   If the vector is supposed to handle duplicate items  I think youre better of implementing your own sort routine

User · Answer

I wrote generic version of index sort   template  lt class RAIter  class Compare gt  void argsort RAIter iterBegin  RAIter iterEnd  Compare comp       std  vector lt size t gt  amp  indexes         std  vector lt  std  pair lt size t RAIter gt   gt  pv       pv reserve iterEnd - iterBegin         RAIter iter       size t k       for  iter   iterBegin  k   0   iter    iterEnd   iter    k              pv push back  std  pair lt int RAIter gt  k iter                 std  sort pv begin    pv end               amp comp  const std  pair lt size t RAIter gt  amp  a  const std  pair lt size t RAIter gt  amp  b  - gt  bool            return comp  a second   b second              indexes resize pv size          std  transform pv begin    pv end    indexes begin                const std  pair lt size t RAIter gt  amp  a  - gt  size t   return a first            Usage is the same as that of std  sort except for an index container to receive sorted indexes  testing   int a       3  1  0  4     std  vector lt size t gt  indexes   argsort a  a   sizeof a    sizeof a 0    std  less lt int gt     indexes    for  size t i   indexes  printf   d n   int i       you should get 2 1 0 3  for the compilers without c  0x support  replace the lamba expression as a class template   template  lt class RAIter  class Compare gt   class PairComp   public    Compare comp     PairComp Compare comp     comp comp        bool operator    const std  pair lt size t RAIter gt  amp  a       const std  pair lt size t RAIter gt  amp  b  const   return comp  a second   b second                    and rewrite std  sort as  std  sort pv begin    pv end    PairComp comp

User · Answer

You could sort std  pair instead of just ints - first int is original data  second int is original index  Then supply a comparator that only sorts on the first int  Example   Your problem instance  v    5 7 8  New problem instance  v prime     lt 5 0 gt    lt 8 1 gt    lt 7 2 gt     Sort the new problem instance using a comparator like   typedef std  pair lt int int gt  mypair  bool comparator   const mypair amp  l  const mypair amp  r       return l first  lt  r first       forgetting the syntax here but intent is clear enough   The result of std  sort on v prime  using that comparator  should be   v prime     lt 5 0 gt    lt 7 2 gt    lt 8 1 gt     You can peel out the indices by walking the vector  grabbing  second from each std  pair

User · Answer

For this type of question Store the orignal array data into a new data and then binary search the first element of the sorted array into the duplicated array and that indice should be stored into a vector or array   input array  gt a duplicate array  gt b vector  gt c Stores the indices position  of the orignal array Syntax  for i 0 i lt n i    c push back binarysearch b n a i        Here binarysearch is a function which takes the array size of array searching item and would return the position of the searched item

User · Answer

vector lt pair lt int int gt   gt a   for  i   0  i  lt  n   i             filling the original array     cin  gt  gt  k      a push back  make pair  k i       k   value  i   original index    sort  a begin   a end      for  i   0   i  lt  n   i         cout  lt  lt  a i  first  lt  lt       lt  lt  a i  second  lt  lt    n       Now a contains both both our values and their respective indices in the sorted   a i  first   value at i th   a i  second   idx in initial array

User · Answer

Consider using std  multimap as suggested by  Ulrich Eckhardt  Just that the code could be made even simpler   Given  std  vector lt int gt  a    5  2  1  4  3       a  5 2 1 4 3   To sort in the mean time of insertion  std  multimap lt int  std  size t gt  mm  for  std  size t i   0  i    a size      i      mm insert  a i   i      To retrieve values and original indices  std  vector lt int gt  b  std  vector lt std  size t gt  c  for  const auto  amp  kv   mm        b push back kv first                  b  1 2 3 4 5     c push back kv second                 c  2 1 4 3 0     The reason to prefer a std  multimap to a std  map is to allow equal values in original vectors  Also please note that  unlike for std  map  operator   is not defined for std  multimap

User · Answer

There is another way to solve this  using a map   vector lt double gt  v             input data map lt double  unsigned gt  m     mapping from value to its index for  auto it   v begin    it    v end      it      m  it    it - v begin      This will eradicate non-unique elements though  If that s not acceptable  use a multimap   vector lt double gt  v             input data multimap lt double  unsigned gt  m     mapping from value to its index for  auto it   v begin    it    v end      it      m insert make pair  it  it - v begin        In order to output the indices  iterate over the map or multimap   for  auto it   m begin    it    m end      it      cout  lt  lt  it- gt second  lt  lt  endl

User · Answer

I came across this question  and figured out sorting the iterators directly would be a way to sort the values and keep track of indices  There is no need to define an extra container of pairs of   value  index   which is helpful when the values are large objects  The iterators provides the access to both the value and the index         a function object that allows to compare    the iterators by the value they point to     template  lt  class RAIter  class Compare  gt  class IterSortComp       public          IterSortComp   Compare comp    m comp   comp               inline bool operator      const RAIter  amp  i  const RAIter  amp  j   const                       return m comp     i    j                  private          const Compare m comp      template  lt class INIter  class RAIter  class Compare gt  void itersort   INIter first  INIter last  std  vector  lt  RAIter  gt   amp  idx  Compare comp          idx resize   std  distance   first  last          for   typename std  vector  lt  RAIter  gt   iterator j   idx begin     first    last     j     first             j   first       std  sort   idx begin     idx end     IterSortComp lt  RAIter  Compare  gt    comp          as for the usage example   std  vector  lt  int  gt  A   n        populate A with some random values std  generate   A begin     A end     rand     std  vector  lt  std  vector  lt  int  gt   const iterator  gt  idx  itersort   A begin     A end     idx  std  less  lt  int  gt           now  for example  the 5th smallest element in the sorted vector would have value   idx  5   and its index in the original vector would be distance  A begin      idx  5     or simply  idx  5   - A begin

User · Answer

Suppose Given vector is   A  2 4 3    Create a new vector  V  0 1 2     indicating positions   Sort V and while sorting instead of comparing elements of V   compare corresponding elements of A     Assume A is a given vector with N elements  vector lt int gt  V N    int x 0   std  iota V begin   V end   x       Initializing  sort  V begin   V end      amp   int i int j  return A i  lt A j

User · Answer

There are many ways  A rather simple solution is to use a 2D vector    include  lt algorithm gt   include  lt iostream gt   include  lt vector gt  using namespace std   int main      vector lt vector lt double gt  gt  val and id   val and id resize 5    for  int i   0  i  lt  5  i         val and id i  resize 2      one to store value  the other for index         Store value in dimension 1  and index in the other      say values are 5 4 7 1 3   val and id 0  0    5 0   val and id 1  0    4 0   val and id 2  0    7 0   val and id 3  0    1 0   val and id 4  0    3 0    val and id 0  1    0 0   val and id 1  1    1 0   val and id 2  1    2 0   val and id 3  1    3 0   val and id 4  1    4 0    sort val and id begin    val and id end         display them   cout  lt  lt   Index  t   lt  lt   Value  n    for  int i   0  i  lt  5  i        cout  lt  lt  val and id i  1   lt  lt    t   lt  lt  val and id i  0   lt  lt    n       return 0      Here is the output      Index   Value    3       1    4       3    1       4    0       5    2       7

User · Answer

Make a std  pair in function then sort pair     generic version     template lt  class RandomAccessIterator class Compare  gt  auto sort2 RandomAccessIterator begin RandomAccessIterator end Compare cmp  - gt     std  vector lt std  pair lt std  uint32 t RandomAccessIterator gt  gt        using valueType typename std  iterator traits lt RandomAccessIterator gt   value type      using Pair std  pair lt std  uint32 t RandomAccessIterator gt        std  vector lt Pair gt  index pair      index pair reserve std  distance begin end         for uint32 t idx 0 begin  end   begin   idx           index pair push back Pair idx begin               std  sort  index pair begin   index pair end     amp   const Pair amp  lhs const Pair amp  rhs             return cmp  lhs second  rhs second                return index pair      ideone

User · Answer

Beautiful solution by  Lukasz Wiklendt  Although in my case I needed something more generic so I modified it a bit   template  lt class RAIter  class Compare gt  vector lt size t gt  argSort RAIter first  RAIter last  Compare comp       vector lt size t gt  idx last-first     iota idx begin    idx end    0      auto idxComp     amp first comp  size t i1  size t i2          return comp first i1   first i2            sort idx begin    idx end    idxComp      return idx      Example  Find indices sorting a vector of strings by length  except for the first element which is a dummy   vector lt string gt  test     dummy    a    abc    ab     auto comp      const string  amp a  const string amp  b        return a length    gt  b length        const auto amp  beginIt   test begin     1  vector lt size t gt  ind   argSort beginIt  test end    comp    for auto i   ind      cout  lt  lt  beginIt i   lt  lt  endl    prints   abc ab a

User · Answer

Using C   11 lambdas    include  lt iostream gt   include  lt vector gt   include  lt numeric gt          std  iota  include  lt algorithm gt        std  sort  std  stable sort  using namespace std   template  lt typename T gt  vector lt size t gt  sort indexes const vector lt T gt   amp v          initialize original index locations   vector lt size t gt  idx v size       iota idx begin    idx end    0         sort indexes based on comparing values in v      using std  stable sort instead of std  sort      to avoid unnecessary index re-orderings      when v contains elements of equal values    stable sort idx begin    idx end             amp v  size t i1  size t i2   return v i1   lt  v i2         return idx      Now you can use the returned index vector in iterations such as  for  auto i  sort indexes v       cout  lt  lt  v i   lt  lt  endl      You can also choose to supply your original index vector  sort function  comparator  or automatically reorder v in the sort indexes function using an extra vector

User · Answer

If it s possible  you can build the position array using find function  and then sort the array   Or maybe you can use a map where the key would be the element  and the values a list of its position in the upcoming arrays  A  B and C   It depends on later uses of those arrays

User · Answer

Well  my solution uses residue technique  We can place the values under sorting in the upper 2 bytes and the indices of the elements - in the lower 2 bytes   int myints      32 71 12 45 26 80 53 33    for  int i   0  i  lt  8  i       myints i    myints i   1  lt  lt  16    i    Then sort the array myints as usual   std  vector lt int gt  myvector myints  myints 8   sort myvector begin    myvector begin   8  std  less lt int gt        After that you can access the elements  indices via residuum  The following code prints the indices of the values sorted in the ascending order   for  std  vector lt int gt   iterator it   myvector begin    it    myvector end      it     std  cout  lt  lt       lt  lt    it   1  lt  lt  16     Of course  this technique works only for the relatively small values in the original array myints  i e  those which can fit into upper 2 bytes of int   But it has additional benefit of distinguishing identical values of myints  their indices will be printed in the right order

[c++] C++ sorting and keeping track of indexes

Examples related to c++

Examples related to sorting

Examples related to stl

Examples related to indexing