Reordering an array based on sorted indices in another array

Question

I'm doing a binary radix sort algorithm assignment and have trouble with the last step. From the instructions I have been given, I know what I have to do, but don't know how to implement it in C++. To better understand what I'm asking, I'll give an example. Let's say we have an array of integers:

int array[5] = {5, 24, 8, 9, 10}

With the value 5 at index 0, 24 at index 2 etc. Now let's say I put those indices in an array and reorder them (in my case, sort them)

int indices[5] = {3, 4, 0, 1, 2}

What I need to do is, based on these reordered indices, reorder the initial array. So for example, since the index 3 is now at index 0 in its array, I have to move 9, which in my example is at index 3, to index 1 in its array as well. The final array would look something like this:

array[5] = {9, 10, 5, 24, 8}

I'm not sure what this is called, so I have trouble finding it online. Does someone know the answer to this problem? Thanks!

Answer 1

There's actually an algorithm to do this in-place, assuming you can also modify the indices array. The algorithm can be summarized as follows:

• Consider index i, you want to put array[indices[i]] into array[i]. To avoid overwriting array[i], let's first store it in another variable value.

• Now that we've used array[indices[i]], we can safely overwrite it with the value we want in index indices[i], which is array[indices[indices[i]]].

• Repeat this process, and eventually we'll get to an index j such that indices[j] == i. We can just do array[j] = value. The reason such j exists is that: a permutation can always be decomposed into a set of "cycles". See the Wikipedia article on permutations for more information.

• Repeat the above steps for every other index that has not been processed yet. We can use the indices array to keep track of which indices have been processed.

The whole algorithm has a time complexity of O(n), where n is the length of the array. It only requires O(1) additional storage (the value variable).

Here's the C++ implementation of the algorithm:

#include <iostream>

int main() {
    const int N = 5;
    int array[N] = {5, 24, 8, 9, 10};
    int indices[N] = {3, 4, 0, 1, 2};
    // After processing index `i`, mark the index by setting `indices[i] = -1`.

    for (int i = 0; i < N; ++i) {
        if (indices[i] == -1) continue;  // index `i` has been processed, skip
        int value = array[i];
        int x = i, y = indices[i];  // `x` is the current index, `y` is the "target" index
        while (y != i) {
            indices[x] = -1;  // mark index as processed
            array[x] = array[y];
            x = y;
            y = indices[x];
        }
        // Now `x` is the index that satisfies `indices[x] == i`.
        array[x] = value;
        indices[x] = -1;
    }

    for (int i = 0; i < N; ++i)
        std::cout << array[i] << " ";
    std::cout << std::endl;
}

Answer 2

Assuming you don't have to do this in-place:

const int len = 5;
int newArray[len];

for(int i=0; i < len; ++i)
{
  newArray[i] = array[indices[i]];
}

memcpy(array,newArray,len * sizeof(int));