# Reorder an array according to given indexes

Given two integer arrays of same size, “arr[]” and “index[]”, reorder elements in “arr[]” according to given index array. It is not allowed to given array arr’s length.

Example:

```Input:  arr[]   = [10, 11, 12];
index[] = [1, 0, 2];
Output: arr[]   = [11, 10, 12]
index[] = [0,  1,  2]

Input:  arr[]   = [50, 40, 70, 60, 90]
index[] = [3,  0,  4,  1,  2]
Output: arr[]   = [40, 60, 90, 50, 70]
index[] = [0,  1,  2,  3,   4]
```

Expected time complexity O(n) and auxiliary space O(1)

We strongly recommend you to minimize your browser and try this yourself first.

A Simple Solution is to use an auxiliary array temp[] of same size as given arrays. Traverse the given array and put all elements at their correct place in temp[] using index[]. Finally copy temp[] to arr[] and set all values of index[i] as i.

## C++

 `// C++ program to sort an array according to given ` `// indexes ` `#include ` ` `  `using` `namespace` `std; ` ` `  `// Function to reorder elements of arr[] according ` `// to index[] ` `void` `reorder(``int` `arr[], ``int` `index[], ``int` `n) ` `{ ` `    ``int` `temp[n]; ` ` `  `    ``// arr[i] should be present at index[i] index ` `    ``for` `(``int` `i=0; i

## Java

 `//Java to find positions of zeroes flipping which ` `// produces maximum number of consecutive 1's ` ` `  `import` `java.util.Arrays; ` ` `  `class` `Test ` `{ ` `    ``static` `int` `arr[] = ``new` `int``[]{``50``, ``40``, ``70``, ``60``, ``90``}; ` `    ``static` `int` `index[] = ``new` `int``[]{``3``,  ``0``,  ``4``,  ``1``,  ``2``}; ` `     `  `    ``// Method to reorder elements of arr[] according ` `    ``// to index[] ` `    ``static` `void` `reorder() ` `    ``{ ` `        ``int` `temp[] = ``new` `int``[arr.length]; ` `      `  `        ``// arr[i] should be present at index[i] index ` `        ``for` `(``int` `i=``0``; i

## Python3

 `# Python 3 program to sort ` `# an array according to given ` `# indexes ` ` `  `# Function to reorder ` `# elements of arr[] according ` `# to index[] ` `def` `reorder(arr,index, n): ` ` `  `    ``temp ``=` `[``0``] ``*` `n; ` ` `  `    ``# arr[i] should be ` `        ``# present at index[i] index ` `    ``for` `i ``in` `range``(``0``,n): ` `        ``temp[index[i]] ``=` `arr[i] ` ` `  `    ``# Copy temp[] to arr[] ` `    ``for` `i ``in` `range``(``0``,n): ` `        ``arr[i] ``=` `temp[i] ` `        ``index[i] ``=` `i ` `     `  `# Driver program ` `arr ``=` `[``50``, ``40``, ``70``, ``60``, ``90``] ` `index ``=` `[``3``, ``0``, ``4``, ``1``, ``2``] ` `n ``=` `len``(arr) ` ` `  `reorder(arr, index, n) ` ` `  `print``(``"Reordered array is:"``) ` `for` `i ``in` `range``(``0``,n): ` `    ``print``(arr[i],end ``=` `" "``) ` ` `  `print``(````" Modified Index array is:"````) ` `for` `i ``in` `range``(``0``,n): ` `    ``print``(index[i],end ``=` `" "``) ` ` `  `# This code is contributed by ` `# Smitha Dinesh Semwal `

## C#

 `// C# to find positions of zeroes flipping which ` `// produces maximum number of consecutive 1's ` `using` `System;  ` `  `  `public` `class` `Test{ ` `     `  `    ``static` `int` `[]arr = ``new` `int``[]{50, 40, 70, 60, 90}; ` `    ``static` `int` `[]index = ``new` `int``[]{3,  0,  4,  1,  2}; ` `      `  `    ``// Method to reorder elements of arr[] according ` `    ``// to index[] ` `    ``static` `void` `reorder() ` `    ``{ ` `        ``int` `[]temp = ``new` `int``[arr.Length]; ` `       `  `        ``// arr[i] should be present at index[i] index ` `        ``for` `(``int` `i=0; i

## PHP

 ` `

Output:

```Reordered array is:
40 60 90 50 70
Modified Index array is:
0 1 2 3 4
```

Thanks to gccode for suggesting above solution.

We can solve it Without Auxiliary Array. Below is algorithm.

```1) Do following for every element arr[i]
a) While index[i] is not equal to i
(i)  Store array and index values of the target (or
correct) position where arr[i] should be placed.
The correct position for arr[i] is index[i]
(ii) Place arr[i] at its correct position. Also
update index value of correct position.
(iii) Copy old values of correct position (Stored in
step (i)) to arr[i] and index[i] as the while
loop continues for i.
```

Below is implementation of above algorithm.

## C++

 `// A O(n) time and O(1) extra space C++ program to ` `// sort an array according to given indexes ` `#include ` ` `  `using` `namespace` `std; ` ` `  `// Function to reorder elements of arr[] according ` `// to index[] ` `void` `reorder(``int` `arr[], ``int` `index[], ``int` `n) ` `{ ` `    ``// Fix all elements one by one ` `    ``for` `(``int` `i=0; i

## Java

 `//A O(n) time and O(1) extra space Java program to ` `//sort an array according to given indexes ` ` `  `import` `java.util.Arrays; ` ` `  `class` `Test ` `{ ` `    ``static` `int` `arr[] = ``new` `int``[]{``50``, ``40``, ``70``, ``60``, ``90``}; ` `    ``static` `int` `index[] = ``new` `int``[]{``3``,  ``0``,  ``4``,  ``1``,  ``2``}; ` `     `  `    ``// Method to reorder elements of arr[] according ` `    ``// to index[] ` `    ``static` `void` `reorder() ` `    ``{ ` `        ``// Fix all elements one by one ` `        ``for` `(``int` `i=``0``; i

## Python3

 `# A O(n) time and O(1) extra space Python3 program to ` `# sort an array according to given indexes ` ` `  `# Function to reorder elements of arr[] according ` `# to index[] ` `def` `reorder(arr, index, n): ` ` `  `    ``# Fix all elements one by one ` `    ``for` `i ``in` `range``(``0``,n): ` ` `  `           ``#  While index[i] and arr[i] are not fixed ` `           ``while` `(index[i] !``=` `i): ` `         `  `               ``# Store values of the target (or correct)  ` `               ``# position before placing arr[i] there ` `               ``oldTargetI ``=` `index[index[i]] ` `               ``oldTargetE ``=` `arr[index[i]] ` ` `  `               ``# Place arr[i] at its target (or correct) ` `               ``# position. Also copy corrected index for ` `               ``# new position ` `               ``arr[index[i]] ``=` `arr[i] ` `               ``index[index[i]] ``=` `index[i] ` ` `  `               ``# Copy old target values to arr[i] and ` `               ``# index[i] ` `               ``index[i] ``=` `oldTargetI ` `               ``arr[i] ``=` `oldTargetE ` ` `  ` `  `# Driver program ` `arr ``=` `[``50``, ``40``, ``70``, ``60``, ``90``] ` `index``=` `[``3``, ``0``, ``4``, ``1``, ``2``] ` `n ``=` `len``(arr) ` ` `  `reorder(arr, index, n) ` ` `  `print``(``"Reordered array is:"``) ` `for`  `i ``in` `range``(``0``, n): ` `    ``print``(arr[i],end``=``" "``) ` ` `  `print``(````" Modified Index array is:"````) ` `for` `i ``in` `range``(``0``, n): ` `    ``print``(index[i] ,end``=``" "``) ` ` `  `# This code is contributed by ` `# Smitha Dinesh Semwal `

## C#

 `//A O(n) time and O(1) extra space C# program to ` `//sort an array according to given indexes ` `using` `System;  ` ` `  `public` `class` `Test ` `{ ` `    ``static` `int` `[]arr = ``new` `int``[]{50, 40, 70, 60, 90}; ` `    ``static` `int` `[]index = ``new` `int``[]{3,  0,  4,  1,  2}; ` `      `  `    ``// Method to reorder elements of arr[] according ` `    ``// to index[] ` `    ``static` `void` `reorder() ` `    ``{ ` `        ``// Fix all elements one by one ` `        ``for` `(``int` `i=0; i

Output:

```Reordered array is:
40 60 90 50 70
Modified Index array is:
0 1 2 3 4
```

Thanks to shyamala_lokre for suggesting above solution.

Another Method without using auxiliary array is to sort the arrays.
Sort the index array and customize the sort to swap the arr[] data whenever you swap the index[] data.

 `//C++ code to reorder an array according to given indices ` `#include ` ` `  `using` `namespace` `std; ` ` `  `int` `heapSize; ` ` `  `void` `swap ( ``int` `&a, ``int` `&b ) { ` `    ``int` `temp = a; ` `    ``a = b; ` `    ``b = temp; ` `} ` ` `  `void` `heapify( ``int` `arr[], ``int` `index[], ``int` `i )  ` `{ ` `    ``int` `largest = i; ` `    ``// left child in 0 based indexing ` `    ``int` `left = 2 * i + 1;  ` `    ``// right child in 1 based indexing ` `    ``int` `right = 2 * i + 2;  ` `    ``// find largest index from root, left and right child ` `    ``if``( left < heapSize && index[left] > index[largest] ) ` `    ``{ ` `        ``largest = left; ` `    ``} ` `    ``if``( right < heapSize && index[right] > index[largest] )  ` `    ``{ ` `        ``largest = right; ` `    ``} ` `     `  `    ``if` `( largest != i ) { ` `        ``//swap arr whenever index is swapped ` `        ``swap(arr[largest], arr[i]);  ` `        ``swap(index[largest], index[i]); ` `        ``heapify(arr, index, largest); ` `    ``} ` `} ` ` `  `void` `heapSort( ``int` `arr[], ``int` `index[], ``int` `n ) { ` `// Build heap ` `    ``for` `( ``int` `i = ( n - 1 ) / 2 ; i >= 0 ; i-- ) { ` `        ``heapify(arr, index, i); ` `    ``} ` `    ``// Swap the largest element of index(first element) ` `    ``// with the last element ` `    ``for` `( ``int` `i = n - 1 ; i > 0 ; i-- ) { ` `        ``swap(index[0], index[i]); ` `        ``//swap arr whenever index is swapped ` `        ``swap(arr[0], arr[i]);  ` `        ``heapSize--; ` `        ``heapify(arr, index, 0); ` `    ``} ` `} ` ` `  `// Driver Code ` `int` `main() { ` `    ``int` `arr[] = {50, 40, 70, 60, 90}; ` `    ``int` `index[] = {3,  0,  4,  1,  2}; ` `    ``int` `n = ``sizeof``(arr)/``sizeof``(arr[0]); ` `    ``heapSize = n; ` `    ``heapSort(arr, index, n); ` ` `  `    ``cout << ````"Reordered array is: "````; ` `    ``for` `( ``int` `i = 0 ; i < n ; i++ ) ` `        ``cout << arr[i] << ``" "``; ` `         `  `        ``cout << ````" Modified Index array is: "````; ` `    ``for` `(``int` `i=0; i

Output:

```Reordered array is:
40 60 90 50 70
Modified Index array is:
0 1 2 3 4
```

Time Compexity: O(nlogn)

## tags:

Arrays STL Arrays STL