Reorder an array according to the given indexes

Given an Input array and the array of indexes, reorder the elements in the input array according to the index array

Example

Input : arr[] = [23,24,25] and given indexes are index[] = [1,0,2]

23 should be moved to Index 1. 24 should be moved to Index 0 and 25 should be at Index 2.

Output : arr[] = [24,23,25]

In the above example, the output array will have 23 in index 1, 24 in index 0 and 25 in index 2.

Time Complexity:O(n)
Auxiliary space: O(1)

Algorithm1

Till the end of the array, pick each element
while index[i] is not equal to i
    a. swap the elements at arr[i] and arr[index[i]]
    b. swap the indexes at index[i], index[index[i]]

C++ Program

#include <bits/stdc++.h>
using namespace std;
int main()
{
	int arr[] ={ 50, 40, 70, 60, 90}; //array
	int index[] = {3,0,4,1,2};//indices for reordering
	int N = sizeof(arr)/sizeof(arr[0]); //size of array
	
	for(int i=0; i<N;i++)
		while(index[i] != i) //keep looping till index[i] is not equal to actual index
		{
			swap(arr[i],arr[index[i]]); //swap both the elements
			swap(index[i],index[index[i]]);	//swap both the indices
		}	
		
	
	for(int i=0;i<N;i++)
		cout<<arr[i] <<" ";
}
Try It

Algorithm 2

Creating an auxilary array to store the final result
Till the end of the array
1. Place the elements in auxilary array, according to the index by going to that index
    ie, auxilary array[index[i]]= arr[i]

C++ Program

#include <bits/stdc++.h>
using namespace std;
int main()
{
	int arr[] ={ 50, 40, 70, 60, 90}; //array
	int index[] = {3,0,4,1,2};//indices for reordering
	int N = sizeof(arr)/sizeof(arr[0]); //size of array
	int final[N];//create an auxiliary array to store the final result
	for(int i=0; i<N;i++)
		final[index[i]]	= arr[i]; //place the elements according to index by going to that index
		
	for(int i=0;i<N;i++)
		cout<<final[i] <<" ";
}	
Try It


Next > < Prev
Scroll to Top