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.

 

Download   Run Code

Output:

5 4 2 1 3

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

 

Download   Run Code

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:

 

Download   Run Code

Output:

5 4 2 1 3

 
1 Star2 Stars3 Stars4 Stars5 Stars (3 votes, average: 5.00 out of 5)

Loading...

Thanks for reading.

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 🙂
 


Leave a Reply

avatar
  Subscribe  
newest oldest most voted
Notify of
Mohammad
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;
}