Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Sort a matrix defined as a vector<double>

Assume I have a square matrix A of size n, defined as a std::vector<double>.

std::vector<double> A(n*n);

The elements of the matrix are accessed the usual way:

double a_ij = A[i*n + j];

I need to sort the rows of the matrix in ascending order with respect to the first column.

The qsort function allows me to do it with arrays and function pointers, but I would like to find a way to accomplish this with vectors and std::sort.

Also, note that I do not wish to define my matrix as a vector of vectors for performance reasons.

Edit:

The function I passed to qsort:

static int comparisonFunction(const void* firstRow, const void* secondRow) 
{
    if (((double *)firstRow)[0] < ((double *)secondRow)[0]) return -1;
    else if (((double *)secondRow)[0] < ((double *)firstRow)[0]) return 1;
    return 0;
}

And the call:

std::qsort(matrixArray, nbRows, sizeof(double)*nbRows, comparisonFunction);
like image 673
Dooggy Avatar asked Nov 03 '16 09:11

Dooggy


1 Answers

std::sort works on iterators, and doesn't care about the iterator implementation. Hence, if you define a struct RowIter which wraps a std::vector<double>& matrix, with a member size_t RowSize for operator+(size_t) (and operator-, operator++ etc) and a Row operator*() const, then std::sort can sort by that iterator.

Still quite a bit more work than qsort, unfortunately, but it would generalize to non-POD types.

like image 169
MSalters Avatar answered Sep 19 '22 17:09

MSalters