Array according to given indexes -2

Software Development
#1

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)