Sort an array in place according to a sort order defined in another array

Question

I have an array that defines the sort order for another array. For example, to sort an array consisting of char * data[] = {"c", "b", "a"};, the sort_order array would be {2, 1, 0} - when the array is sorted, the first element should be "c" (which is data[sort_order[0]]).

(The background for this is that I have two arrays which I want to sort, but the second array should use the same sort order as the first one. So basically I sort {0, 1, 2} using the values from the first array, and then I'd use this sort order to sort the actual values of both arrays.)

The obvious solution would be to create a copy of the array (new_data), and then assign every element the correct value as defined by the sort order:

for (int i = 0; i < n; ++i)
{
    new_data[i] = data[sort_order[i]];
}

However, this requires making a copy of the array. Is there a way I can swap the elements of the original array to sort them in place without having to copy the array?

Edit: The "possible duplicate" does use another array, which is precisely what I am trying to avoid.

Does the question In place array reordering help?

Jonathan Leffler
– Jonathan Leffler

2016-06-11 05:44:38 +00:00
Commented Jun 11, 2016 at 5:44 — Jonathan Leffler
– Jonathan Leffler, Commented Jun 11, 2016 at 5:44

rcgldr · Accepted Answer · 2016-06-11 23:20:23Z

1

Reorder in place, sorts both A[] and I[], by rotating "cycles". Each store places a value in it's proper location, so time complexity is O(n).

    // reorder A in place according to sorted indices in I
    // tA is temp value for A
    for(i = 0; i < n; i++){
        if(i != I[i]){
            tA = A[i];
            k = i;
            while(i != (j = I[k])){
                A[k] = A[j];
                I[k] = k;
                k = j;
            }
            A[k] = tA;
            I[k] = k;
        }
    }

I just noticed that you're using C. In C++, you can use a lambda compare function to compare members of A[], based on indices in I[]. For C, you can use an array of pointers P[] instead of an array of indices I[].

    /* create array of pointers to A[] */
    for(i = 0; i < n; i++)
        P[i] = &A[i];
    /* sort array of pointers, compare is custom compare function */
    qsort(P, n, sizeof(P[0]), compare);
    /* reorder A[] according to the array of pointers */
    for(i = 0; i < n; i++){
        if(i != P[i]-a){
            tA = A[i];
            k = i;
            while(i != (j = P[k]-a)){
                A[k] = A[j];
                P[k] = &A[k];
                k = j;
            }
            A[k] = tA;
            P[k] = &A[k];
        }
    }

Example custom compare for qsort() if A[] contains integers. Since qsort() passes pointers to P[] as parameters to compare(), and since P[] is an array of pointers, then the passed parameters to compare() are pointers to pointers.

int compare(const void *pp0, const void *pp1)
{
    return( (**(int **)pp0) - (**(int **)pp1) );
}

If the goal is to sort a second array B[], based on sorting A[], then add lines like:

        /* ... just after tA = A[i] */
        tB = B[i];
            /* ... just after A[k] = A[j] */
            B[k] = B[j];
        /* ... just after A[k] = tA */
        B[k] = tB;

edited Jun 11, 2016 at 23:20

answered Jun 11, 2016 at 3:27

rcgldr

29.4k3 gold badges41 silver badges70 bronze badges

Sign up to request clarification or add additional context in comments.

7 Comments

secretpow Over a year ago

Thanks, this seems to work. Can you explain why it works? What do k and j represent?

David C. Rankin Over a year ago

It is just using your sort_order array (array I above) as the second tmp array. If you check, the values in the sort_order array are modified in the process (which is essentially just using it for the temporary array).

rcgldr Over a year ago

@secretpow - k and j are just temporary indices. k starts off as the first index in a "cycle", then its advanced through the "cycle" until it gets to the end of the cycle. For example if I[] = {3, 2, 0, 1}; then k starts off as 0, then gets changed I[0] == 3, then to I[3] == 1, then to I[1] == 2, then to I[2] == 0, ending the cycle. While k is being advanced, the values from both A[] and I[] are copied to their sorted locations. There may be multiple cycles, which is why the outer loop is needed.

rcgldr Over a year ago

@secretpow - to sort multiple arrays according to one of the arrays, you can create and sort an array of indices 0 to n-1 according to one of the arrays. Then use the sorted array of indices to sort all of the arrays (this also returns the indices array back to 0 to n-1). The alternative is to write your own sort program, and perform the same swaps and/or moves to all arrays while using only one of the arrays to determine the sort order.

rcgldr Over a year ago

@secretpow - I updated my answer to include a C example that creates and sorts an array of pointers P[] to A[], then reorders A[] according to P[]. This would allow you to use qsort() with a custom compare function.

|

Collectives™ on Stack Overflow

Sort an array in place according to a sort order defined in another array

1 Answer 1

7 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

7 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related