Posted on by Kalkicode
Code Array

Reorder an array according to given indexes

The problem at hand is to arrange an array according to given indexes. This means we need to reorder the elements of the array based on the positions provided in another index array. The elements of the original array will be moved to their respective positions as indicated by the index array. We are required to implement a recursive solution to solve this problem.

Problem Statement and Example

Let's understand the problem with an example. Consider the following arrays:

Original array (arr): 1 2 3 4 5 6 7 8 9 10

Index array (indexes): 5 2 0 7 9 1 6 3 8 4

After reordering the 'arr' array according to the 'indexes' array, the new 'arr' array will be:

3 6 2 8 10 1 7 4 9 5

The element at index 0 in 'arr' is 1, and its position in 'indexes' is 5, so 1 will be moved to index 5 in the new 'arr', and so on for the other elements.

Idea to Solve the Problem

Move array elements from given index

To solve this problem recursively, we can follow the following approach:

  1. Base Case: If the index 'i' becomes equal to or greater than the size of the array, we stop the recursion as all elements have been processed.
  2. Recursive Step: For each element at index 'i', we first store its data in a temporary variable. Then we recursively call the function with 'i+1'. After the recursive call, we put the data at its correct position in the 'arr' array according to 'indexes[i]'.

Pseudocode

display(arr[], size):
    for i from 0 to size-1:
        print arr[i]

reorder(arr[], indexes[], size, i):
    if i >= size:
        return
    data = arr[i]
    reorder(arr, indexes, size, i+1)
    arr[indexes[i]] = data

main():
    arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
    indexes[] = {5, 2, 0, 7, 9, 1, 6, 3, 8, 4}
    size = size of arr
    display(arr, size)
    display(indexes, size)
    reorder(arr, indexes, size, 0)
    display(arr, size)

Algorithm Explanation

  1. The 'display' function is used to print the elements of an array.
  2. The 'reorder' function takes 'arr', 'indexes', 'size', and 'i' as input parameters.
  3. The 'reorder' function first checks if the current index 'i' is greater than or equal to 'size'. If yes, it returns, as it indicates that all elements have been processed.
  4. If the base case is not met, it proceeds with the recursive step: a. It stores the data of the element at index 'i' in a temporary variable 'data'. b. It then makes a recursive call to 'reorder' with 'i+1'. c. After the recursive call is completed, it puts the 'data' at its correct position in the 'arr' array, using 'indexes[i]' as the index.

Output Explanation

The output shows the elements of the original 'arr' array and the 'indexes' array. Then it prints the 'arr' array after reordering. The 'reorder' function recursively reorders the elements based on the 'indexes' array, and the output shows the resulting 'arr' array.

Time Complexity

The time complexity of the provided solution is O(N), where N is the number of elements in the array. This is because each element is visited once during the recursive function calls. The reorder function is called N times, and each call takes constant time operations. Therefore, the overall time complexity is linear in the size of the array.

Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment