Shuffle an array according to the given order of elements

Given an array of distinct integers, shuffle an array according to the given order of elements.

For example,

Input:

arr[] = { 1, 2, 3, 4, 5 }
pos[] = { 3, 2, 4, 1, 0 }

Output:

arr[] = { 5, 4, 2, 1, 3 }

i.e. if pos[i] = j, then update arr[j] = arr[i] for every index i.
In other words, update arr[pos[i]] = arr[i] for every index i.

Simple solution is to create an auxiliary array of size n and for each element in the input array, we set the corresponding values in the auxiliary array. After filling the auxiliary array, we copy it back to the given array. This can be implemented as follows in C.

Output:

5 4 2 1 3

We can also use a map in place of the auxiliary array as demonstrated below in C++:

Output:

5 4 2 1 3

Both above solutions take extra space. The algorithm can be implemented with O(1) extra space as shown below:

Output:

5 4 2 1 3

(3 votes, average: 5.00 out of 5)

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂

Subscribe
Notify of
Guest

/******************************************************************************

Online C++ Compiler.
Code, Compile, Run and Debug C++ program online.
Write your code in this editor and press “Run” button to compile and execute it.

*******************************************************************************/

#include
#include

using namespace std;

void quickSort(int pos[], int arr[], int left, int right) {

int i = left, j = right;
int tmp;
int pivot = pos[(left + right) / 2];
while (i <= j) {
while (pos[i] pivot)
j–;
if (i <= j) {
tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
tmp = pos[i];
pos[i]=pos[j];
pos[j]=tmp;
i++;
j–;
}
};

if (left < j)
quickSort(pos, arr, left, j);

if (i < right)
quickSort(pos,arr, i, right);

}
void reshuffle(int arr[], int pos[], int n)
{
quickSort(pos, arr,0,n-1);
}
int main()
{
int arr[]={1, 2, 3, 4, 5};
int pos[]={3, 2, 4, 1, 0};
int n = sizeof(arr)/sizeof(arr[0]);
reshuffle(arr, pos, n);
for(int i=0; i<5; i++)
cout<<arr[i]<<endl;
cout<<"Hello World";

return 0;
}