Another Method without using an 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 <bits/stdc++.h>
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: \n" ;
`` for ( int i = 0 ; i < n ; i++ )
`` cout << arr[i] << " " ;
``
`` cout << "\nModified Index array is: \n" ;
`` for ( int i=0; i<n; i++)
`` cout << index[i] << " " ;
`` return 0;
}
Output:
Reordered array is: 40 60 90 50 70
Modified Index array is: 0 1 2 3 4
Time Complexity: O(nlogn)