C++, Sorting Separate Arrays Simultaneously

Question

Consider the case where “rowPtr”, “colInd” and “values” in a struct are dynamically allocated with same number of elements. In this scenario, what is the fastest way (without copying if possible!!) to sort elements of colInd so that rowPtr and value elements are swapped or change positions based on how elements of colInd change positions.

struct csr
{
    int rows;
    int cols;
    int nzmax;
    int *rowPtr;
    int *colInd;
    double *values;
};
// A simple example without a struct. Just based on arrays
double values[10] = {0.2135, 0.8648, 7, 0.3446, 0.1429, 6, 0.02311, 0.3599, 0.0866, 8 };
int rowPtr[10] = { 0, 3, 6, 10, 2 -1, 24, -4, 1, 11 };
int colInd[10] = { 0, 2, 4, 1, 2, 3, 0, 1, 2, 4 };
// sort colInd and simultaneously change positions in rowPtr and values
//After sorting
Values = {0.214, 0.023, 0.345, 0.360, 0.865, 0.143, 0.087, 6.0};
rowPtr = {0, 24, 10, -4, 3, 2, 1, -1};
colInd  = {0, 0, 1, 1, 2, 2, 2, 3};

Whenever you do a change in `collnd` do the equivalent change in the others. Am I misunderstanding you? — ChiefTwoPencils, Feb 09 '15 at 05:02
If possible, reconsider your data structure. Have a struct with three members (two ints and one double), have `csr` hold an array (or better still, `std::vector`) of these structs. Then you can just use `std::sort` with a suitable comparison predicate. — Igor Tandetnik, Feb 09 '15 at 05:03
Though I do not like it a struct has become a necessity as it is required format for a previously created C library — Vineet Yadav, Feb 09 '15 at 05:07

score 0 · Answer 1 · answered Feb 09 '15 at 05:12

I suggest putting the three arrays into an array of struct and sorting the array of struct.

struct csr_data
{
    int rowPtr;
    int colInd;
    double value;
};

and

struct csr
{
    int rows;
    int cols;
    int nzmax;
    csr_data* data_array;
};

You can sort an array of csr_data using any of the three member variables. When they are sorted, all elements of csr_data will be rearranged regardless of which member you use to sort the data by.

C++, Sorting Separate Arrays Simultaneously

1 Answers1