# Reorder array using given indexes

## Given two input arrays of same size, second array is index array, we need to reorder elements in same array according to given index array.

### Example

a)    Input
array : [4, 2, 1, 3]
index : [3, 1, 0, 2]

Output
array : [1, 2, 3, 4]
index : [0, 1, 2, 3]
Here, given index array is [3, 1, 0, 2],
Therefore, array[3] = 4
array[1] = 2
array[0] = 1
array[2] = 3
Output will be: [1, 2, 3, 4]

b)    Input
array : [9, 5, 3, 7, 11, 1]
index : [4, 2, 1, 0, 3, 5]

Output
array : [7, 3, 5, 11, 8, 9, 1]
index : [0, 1, 2, 3, 4, 5]

## Method 1

Time complexity : O(n)

## Algorithm

Step 1 : create a function which takes the two input arrays array[] and index[] and reorders based on index array.

Step 2 : In the function,

a)    Create an auxiliary array temp same size of given arrays.
b)    Traverse the given array and put elements at there correct position in temp based on index[]. temp[index[i]] = array[i]
c)    Copy this temp array as given array and change index array based on indexes.

Step 3 : call this function on given input arrays and print the arrays.

## C++ Program

``````#include <bits/stdc++.h>
using namespace std;

//Function for reoreder elements based on index array
void Reorder(int array[], int index[], int N)
{
int temp[N];//auxilary array
//array[i] should present at (index[i]) index
for (int i=0; i<N; i++)
{
temp[index[i]] = array[i];
}
for (int i=0; i<N; i++)
{
array[i] = temp[i];
index[i] = i;
}
}
//function to print the given array
int PrintArray(int array[],int N)
{
for (int i=0; i<N; i++)
{
cout << array[i] << " ";
}
}
//Main function
int main()
{
int array[] = {50, 40, 70, 60, 90};
int index[] = {3,  0,  4,  1,  2};
int N = sizeof(array)/sizeof(array[0]);
cout << "Input array: \n";
PrintArray(array,N);
cout << "\nInput index array: \n";
PrintArray(index,N);
//Reordering by using function
Reorder(array,index,N);

cout << "\nOutput array: \n";
PrintArray(array,N);
cout << "\nOutput index array: \n";
PrintArray(index,N);
return 0;
}``````

## Method 2

Time complexity : O(n)

No auxiliary array

## Algorithm

Step 1 : create a function which takes the given arrays and reorders based on the index array.

Step 2 : If index[i] = i, we need not change the position so, for all elements in the input array.
a)    Store values at correct position array[i] should be placed in dummy variables.
b)    Place array[i] at its position and update index value. (array[index[i]] = array[i])
c)    Copy old values to current positions. array[i] = oldElementvalue and update index.

Step 3 : call this function input arrays, to reorder them.

## C++ Program

``````#include <bits/stdc++.h>
using namespace std;

//Function for reoreder elements based on index array
void Reorder(int array[], int index[], int N)
{
for(int i=0; i<N; i++)
{
while (index[i] != i)
{
//storing correct position values
int  oldIndexValue = index[index[i]];
char oldElementValue   = array[index[i]];
array[index[i]] = array[i];
index[index[i]] = index[i];
index[i] = oldIndexValue;
array[i]   = oldElementValue;
}
}
}
//function to print the given array
int PrintArray(int array[],int N)
{
for (int i=0; i<N; i++)
{
cout << array[i] << " ";
}
}
//Main Function
int main()
{
int array[] = {50, 40, 70, 60, 90};
int index[] = {3,  0,  4,  1,  2};
int N = sizeof(array)/sizeof(array[0]);
cout << "Input array: \n";
PrintArray(array,N);
cout << "\nInput index array: \n";
PrintArray(index,N);
//Reordering by using function
Reorder(array,index,N);

cout << "\nOutput array: \n";
PrintArray(array,N);
cout << "\nOutput index array: \n";
PrintArray(index,N);
return 0;
}``````

Scroll to Top