Home »
Data Structure »
Array Data Structure
Reorder an array according to given indexes
C++ implementation to Reorder an array according to given indexes using multiple approaches.
Submitted by Vikneshwar GK, on March 11, 2022
Consider an integer array, of size n and an index array, of size n, containing index values. The task hand is to sort the array element based on the values of index array, i.e. if index[0] is 2, then place array[0] at index 2.
Example:
Input:
array[]= {1, 2, 3, 4, 5}
index[] = {4, 3, 2, 1, 0}
Output:
array[] = {5, 4, 3, 2, 1}
Input:
array[] = {3, 1, 4, 5, 2}
index[] = {2, 0, 3, 4, 1}
Output:
array[] = {1, 2, 3, 4, 5}
Solution 1: Using Extra Array
This approach uses an additional array to rearrange the elements. Although it is time efficient, this method uses extra space. It involves the following step:
- Declare a temporary variable of size n, where n is the length of the array.
- Iterate the integer array and index arrays and place the elements in the temporary array accordingly, i.e., temp[index[i]] = array[i].
- Print the temporary array.
C++ Implementation:
#include <bits/stdc++.h>
using namespace std;
// Function to print the array
void printArray(int array[], int length)
{
for (int i = 0; i < length; i++) {
cout << array[i] << " ";
}
}
// function to double the element
// based on the conditions
void rearrangeArray(int array[], int index[], int length)
{
// declare temporary array
int temp[length];
// traverse the array
for (int i = 0; i < length; i++) {
temp[index[i]] = array[i];
}
// call function to push the zeros
printArray(array, length);
}
// Main function
int main()
{
int array[100], N, index[100];
cout << "Enter Number of elements: ";
cin >> N;
for (int i = 0; i < N; i++) {
cout << "Enter element " << i + 1 << ": ";
cin >> array[i];
}
for (int i = 0; i < N; i++) {
cout << "Enter index " << i + 1 << ": ";
cin >> index[i];
}
rearrangeArray(array, index, N);
return 0;
}
Output:
Enter Number of elements: 5
Enter element 1: 1
Enter element 2: 2
Enter element 3: 3
Enter element 4: 4
Enter element 5: 5
Enter index 1: 4
Enter index 2: 3
Enter index 3: 2
Enter index 4: 1
Enter index 5: 0
1 2 3 4 5
Time Complexity: O(n), where n is the length of the array.
Solution 2: Using Sort
This method involves sorting the array. The idea here is to sort the index array and whenever you swap the elements of the index array, you also swap the corresponding position elements in the integer array. In this way, the index array will be arranged according to the index array.
We will be using a heap sort which has a time complexity of O(nlog(n)).
C++ Implementation:
#include <bits/stdc++.h>
using namespace std;
// Function to print the array
void printArray(int array[], int length)
{
for (int i = 0; i < length; i++) {
cout << array[i] << " ";
}
}
int heapSize;
void swap(int& num1, int& num2)
{
int temp = num1;
num1 = num2;
num2 = temp;
}
void heapify(int array[], int index[], int i)
{
int max = i;
// 0 based indexing
int left = 2 * i + 1;
// 1 based indexing
int right = 2 * i + 2;
// find max index among root, left and right child
if (left < heapSize && index[left] > index[max]) {
max = left;
}
if (right < heapSize && index[right] > index[max]) {
max = right;
}
if (max != i) {
// swap elements
swap(array[max], array[i]);
swap(index[max], index[i]);
heapify(array, index, max);
}
}
void rearrangeArray(int array[], int index[], int length)
{
// Build heap
for (int i = (length - 1) / 2; i >= 0; i--) {
heapify(array, index, i);
}
// iterate the array from last to first
for (int i = length - 1; i > 0; i--) {
// swap the elements
swap(index[0], index[i]);
swap(array[0], array[i]);
heapSize--;
heapify(array, index, 0);
}
printArray(array, length);
}
// Main Function
int main()
{
int array[100], N, index[100];
cout << "Enter Number of elements: ";
cin >> N;
for (int i = 0; i < N; i++) {
cout << "Enter element " << i + 1 << ": ";
cin >> array[i];
}
for (int i = 0; i < N; i++) {
cout << "Enter index " << i + 1 << ": ";
cin >> index[i];
}
heapSize = N;
rearrangeArray(array, index, N);
return 0;
}
Output:
Enter Number of elements: 5
Enter element 1: 1
Enter element 2: 2
Enter element 3: 3
Enter element 4: 4
Enter element 5: 5
Enter index 1: 4
Enter index 2: 3
Enter index 3: 2
Enter index 4: 1
Enter index 5: 0
5 4 3 2 1
Time Complexity: O(nlog(n)), where n is the length of the array.
Solution 3: Swap till correct position
This is an efficient method that does not use any extra array. The idea here is to swap the array elements according to the index elements until its current position is placed in the correct position. It involves the following steps:
- Iterate through the array
- If index[i] != i, then swap array[i] and array[index[i]] till index[i]=i
- Decrement the value of i
Example:
If the array = {1, 2, 3, 4, 5} and index = {2, 3, 0, 1, 4}
In 1st iteration, index[0] != 0
Swap(array[0], array[2]) => array = {3, 2, 1, 4, 5}
and index = {0, 3, 2, 1, 4}
Perform i--
Since index[0] = 0, proceed to next iteration
In the 2nd iteration, index[1] !=3
Swap(array[1], array[3]) => array = {3, 4, 1, 2, 5}
and index = {0, 1, 2, 3, 4}
Perform i--
Since index[1] = 1, proceed to next iteration
Repeat the above steps for all the elements of the array
C++ Implementation:
#include <bits/stdc++.h>
using namespace std;
void rearrangeArray(int array[], int index[], int length)
{
// iterate the array
for (int i = 0; i < length; i++) {
// swap elements till it is
// placed in correct position
if (index[i] != i) {
swap(array[i], array[index[i]]);
swap(index[i], index[index[i]]);
i--;
}
}
}
// Function to print the array
void printArray(int array[], int length)
{
for (int i = 0; i < length; i++) {
cout << array[i] << " ";
}
}
// Main Function
int main()
{
int array[100], N, index[100];
cout << "Enter Number of elements: ";
cin >> N;
for (int i = 0; i < N; i++) {
cout << "Enter element " << i + 1 << ": ";
cin >> array[i];
}
for (int i = 0; i < N; i++) {
cout << "Enter index " << i + 1 << ": ";
cin >> index[i];
}
rearrangeArray(array, index, N);
printArray(array, N);
return 0;
}
Output:
Enter Number of elements: 5
Enter element 1: 1
Enter element 2: 2
Enter element 3: 3
Enter element 4: 4
Enter element 5: 5
Enter index 1: 4
Enter index 2: 3
Enter index 3: 2
Enter index 4: 1
Enter index 5: 0
5 4 3 2 1
Time Complexity: O(n), where n is the length of the array.