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.