Reorder an array according to given indexes

Software Development
#1

Hello Everyone,

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++ program to sort an array according to given

// indexes

#include<iostream>

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<n; i++)

temp[index[i]] = arr[i];

// Copy temp[] to arr[]

for ( int i=0; i<n; i++)

{

arr[i] = temp[i];

index[i] = i;

}

}

// Driver program

int main()

{

int arr[] = {50, 40, 70, 60, 90};

int index[] = {3, 0, 4, 1, 2};

int n = sizeof (arr)/ sizeof (arr[0]);

reorder(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

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.

// A O(n) time and O(1) extra space C++ program to

// sort an array according to given indexes

#include<iostream>

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<n; i++)

{

// 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

int oldTargetI = index[index[i]];

char 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

int main()

{

int arr[] = {50, 40, 70, 60, 90};

int index[] = {3, 0, 4, 1, 2};

int n = sizeof (arr)/ sizeof (arr[0]);

reorder(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

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)

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above