Sorting two arrays based on one with standard library (copy steps avoided)

Question

I have old code to maintain and I was replacing a custom QuickSort which was sorting two arrays based on array one with std::sort. Is there a way to sort two arrays based one one of them without an additional split step and without implementing a sorting function again? Below is the current example vector1D is basically std::vector.

    vector1D<std::pair<int64_t, uint8_t>> m_RowCol(m_NX * m_NY * m_NZ);
    //..
    std::sort(
        m_RowCol.begin(),
        m_RowCol.end(),
        [](const std::pair<int64_t, uint8_t> &a, const std::pair<int64_t, uint8_t> &b) { return a.first < b.first && (a.first > 0 && b.first > 0); }
    );
    // copy into two vectors
    vector1D<int64_t> m_Row;
    vector1D<uint8_t> m_Col;
    for (auto it = std::make_move_iterator(m_RowCol.begin()), end = std::make_move_iterator(m_RowCol.end()); it != end; ++it)
    {
        m_Row.push_back(std::move(it->first));
        m_Col.push_back(std::move(it->second));
    }
    m_RowCol.clear();

See http://stackoverflow.com/questions/13840998/sorting-zipped-locked-containers-in-c-using-boost-or-the-stl — Igor Tandetnik, May 17 '17 at 14:57
Note though that your comparator doesn't satisfy strict weak ordering requirements, so your program exhibits undefined behavior. Specifically, 0 is equivalent to 1 and 0 is equivalent to 2, but 1 is not equivalent to 2. — Igor Tandetnik, May 17 '17 at 15:00
I would like to avoid 3rd Party libs. Boost may work though. — dgrat, May 17 '17 at 15:17

rcgldr · Answer 1 · 2017-05-18T01:10:52.577

You can create an array of indices, sort the indices according to one of the arrays, then reorder the two arrays and array of indices in place according to the sorted array of indices in O(n) time:

#include <algorithm>
#include <iostream>

int main()
{
int A[8] = {8,6,1,7,5,3,4,2};
char B[8] = {'h','f','a','g','e','c','d','b'};
size_t I[8];
size_t i, j, k;
int ta;
char tb;
    // create array of indices to A[]
    for(i = 0; i < sizeof(A)/sizeof(A[0]); i++)
        I[i] = i;
    // sort array of indices to A[]
    std::sort(I, I+sizeof(I)/sizeof(I[0]),
              [&A](int i, int j) {return A[i] < A[j];});
    // reorder A[] B[] I[] according to I[]
    for(i = 0; i < sizeof(A)/sizeof(A[0]); i++){
        if(i != I[i]){
            ta = A[i];
            tb = B[i];
            k = i;
            while(i != (j = I[k])){
                A[k] = A[j];
                B[k] = B[j];
                I[k] = k;
                k = j;
            }
            A[k] = ta;
            B[k] = tb;
            I[k] = k;
        }
    }
    for(i = 0; i < sizeof(A)/sizeof(A[0]); i++)
        std::cout << A[i] << ' ';
    std::cout << std::endl;
    for(i = 0; i < sizeof(B)/sizeof(B[0]); i++)
        std::cout << B[i] << ' ';
    std::cout << std::endl;
    return 0;
}

or an array of pointers can be used instead of an array of indices, which allows a normal compare function instead of a lambda compare function.

#include <algorithm>
#include <iostream>

bool compare(const int *p0, const int *p1)
{
    return *p0 < *p1;
}

int main()
{
int A[8] = {8,6,1,7,5,3,4,2};
char B[8] = {'h','f','a','g','e','c','d','b'};
int *pA[8];
size_t i, j, k;
int ta;
char tb;
    // create array of pointers to A[]
    for(i = 0; i < sizeof(A)/sizeof(A[0]); i++)
        pA[i] = &A[i];
    // sort array of pointers to A[]
    std::sort(pA, pA+sizeof(A)/sizeof(A[0]), compare);
    // reorder A[] B[] pA[] according to pA[]
    for(i = 0; i < sizeof(A)/sizeof(A[0]); i++){
        if(i != pA[i]-A){
            ta = A[i];
            tb = B[i];
            k = i;
            while(i != (j = pA[k]-A)){
                A[k] = A[j];
                B[k] = B[j];
                pA[k] = &A[k];
                k = j;
            }
            A[k] = ta;
            B[k] = tb;
            pA[k] = &A[k];
        }
    }
    for(i = 0; i < sizeof(A)/sizeof(A[0]); i++)
        std::cout << A[i] << ' ';
    std::cout << std::endl;
    for(i = 0; i < sizeof(B)/sizeof(B[0]); i++)
        std::cout << B[i] << ' ';
    std::cout << std::endl;
    return 0;
}

Sorting two arrays based on one with standard library (copy steps avoided)

1 Answers1

Linked