Sorting indices of a matrix with qsort

TunaPete (24)
I have a matrix, A, and I want to sort the row indices by the second col, but I don't want to change A. I created an array to keep track of the indices and was planing on sorting that array with qsort. Let's look at some code:

1
2
3
4
5
6
 
vector< vector<double> > A;
...// A is given values, A is a n*m matrix (n rows, m col)
int rowIndex[n];
for(int i=0; i<n; i++)
    rowIndexI[i] = i;
qsort(rowIndex, n, sizeof(int), compare);


Here comes the problem, I need A as input in some way to the compare function. Here's what I want i principal:

1
2
3
4
5
6
7
8
 
int compare(const int * a, const int * b);{
   if(A[*a][2]>A[*b][2]){
       return 1;
   }else if(A[*a][2]<A[*b][2]){
       return -1;
   }
   return 0;
}


How can I get the "compare"-function to know A? I would prefer to not make A global, because as I understand it that's bad style.
Last edited on
Duthomhas (13206)
This is where functors really shine.
The other option is simply to make the comparison function a method of A.

For the functor, just make it a class which takes a reference to A:

1
2
3
 
#include <algorithm>
#include <vector>
using namespace std;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 
struct compare_t
  {
  // Our functor takes a reference to the table and a column to use when comparing rows
  vector <vector <double> > & matrix;
  unsigned                    column;

  compare_t(
    vector <vector <double> > & matrix,
    unsigned                    column
    ):
    matrix( matrix ),
    column( column )
    { }

  // This is the comparison function: taking two rows and comparing them
  // by the (previously) specified column
  bool operator () ( const vector <double> & lhrow, const vector <double> & rhrow ) const
    {
    return lhrow.at( column ) < rhrow.at( column );
    }
  };
1
2
3
4
5
6
7
8
9
10
11
12
13
 
// This, of course, is our matrix
vector <vector <double> > A;

// Somewhere in here we fill it in
// Hopefully there will be at least three columns in each row when done...
// (Otherwise the sorting below will throw an exception)
...

// Here we use the STL sorting algorithm with our special functor to
// sort the rows of A by the values in the third column
stable_sort( A.begin(), A.end(), compare_t( A, 2 ) );

// All done!

If your sort doesn't need to preserve ordering for equal elements, then you'll get some advantage by just using the std::sort() algorithm.

Notice how I did not use the old C-library qsort() function. The STL sort algorithms are better. :-)

Hope this helps.
Last edited on
TunaPete (24)
I haven't understood all the details yet, but it looks awesome. Thanks a ton!!!
Last edited on
Duthomhas (13206)
You're welcome.

Beware that I just typed that in. Some revision might be necessary. (So let me know if you are having trouble making it work.)

:-)
Topic archived. No new replies allowed.