Reorder an array according to given indexes in Java
To reorder the elements in an array based on the given index array, you can follow a straightforward approach. Create an auxiliary array called "temp" of the same size as the given arrays. Traverse through the given array and place each element at its correct position in the temp array using the corresponding index from the index array. Finally, copy the elements from the temp array back to the original array and update the index array to reflect the new order.
Example1:
Input: arr[] = [5,8,3,1,9]
index[] = [4,0,3,2,1]
Output: arr[] = [8,9,1,3,5]
index[] = [0,1,2,3,4]
Explanation: The elements in arr[] are reordered based on the given index[] array. The element 5 is indexed at position 4, the element 8 at position 0, the element 3 at position 3, the element 1 at position 2, and the element 9 at position 1. The index[] array is changed to [0,1,2,3,4], and arr[] becomes [8,9,1,3,5].
Example2:
Input: arr[] = [2,7,4,6,3]
index[] = [2,4,1,0,3]
Output: arr[] = [6,4,2,3,7]
index[] = [0, 1, 2, 3, 4]
Explanation: The elements in arr[] are reordered based on the given index[] array. The element 2 is placed at index 2 and element 7 is placed at index 4 and the element 4 is placed at index 1 and the element 6 is placed at index 0 and the element 3 is placed at index 3. After reordering, arr[] becomes [6,4,7,3,2], and the index[] array is updated to [0,1,2,3,4].
Naïve Approach
ALGORITHM:
Step 1: Start the reorder function with the given arrays arr[] and index[].
Step 2: Get the length of the arrays and shop it inside the variable n.
Step 3: Iterate over the elements of the arrays using a loop from i = 0 to n-1.
Step 4: Inside the loop, initialize a temporary variable temp to store the current element arr[i].
Step 5: Also, store the current index value index[i] in a temporary variable tempIndex.
Step 6: Enter a while loop that continues until the current index index[i] is equal to i.
Step 7: Inside the while loop, swap the elements in arr[] and index[] using the current index value.
Step 8: Swap arr[i] with arr[index[i]].
Step 9: Swap index[i] with index[index[i]].
Step 10: After the while loop ends, assign the value of temp to arr[i] to put the correct element in place.
Step 12: Assign the value of tempIndex to index[i] to update the index value.
Step 13: Repeat steps 4-9 for all elements in the arrays.
Step 14: The arrays arr[] and index[] are now reordered based on the given indexes.
Implementation:
The implementation of the above steps given below
FileName: SimpleReorder.java
import java.util.*;
class SimpleReorder {
static void reorder(int[] arr,int[] index)
{
int n=arr.length;
int[] temp=new int[n];
// arr[i] should be present at index[i] index
for (int i=0;i
temp[index[i]]=arr[i];
// Copy temp[] to arr[]
for (int i=0;i
{
arr[i] = temp[i];
index[i] = i;
}
}
public static void main(String[] args)
{
// Example 1
int[] arr1 = {5,8,3,1,9};
int[] index1 = {4,0,3,2,1};
reorder(arr1,index1);
System.out.print("arr[] = ");
for (int element : arr1) {
System.out.print(element + " ");
}
System.out.print("
index[] = ");
for (int element : index1) {
System.out.print(element + " ");
}
System.out.println();
// Example 2
int[] arr2 = {2,7,4,6,3};
int[] index2 = {2,4,1,0,3};
reorder(arr2,index2);
System.out.print("arr[] = ");
for (int element : arr2) {
System.out.print(element + " ");
}
System.out.print("
index[] = ");
for (int element : index2) {
System.out.print(element + " ");
}
}
}
Output:
arr[] = 8 9 1 3 5 index[] = 0 1 2 3 4 arr[] = 6 4 2 3 7 index[] = 0 1 2 3 4
Complexity Analysis:
Time Complexity: The algorithm has a time complexity of O(n) because we traverse the arrays once.
Space Complexity: The algorithm has an auxiliary space complexity of O(1) since we use a constant amount of extra space.
Approach 2: Using Auxiliary array
ALGORITHM:
Step 1: Start by means of iterating over the factors of the arrays arr[] and index[] from 0 to n, where n is the period of the arrays.
Step 2: For every generation check if the modern-day element at index[i] isn't always same to i. The condition indicates that the element is not at its correct position.
Step 3: If the circumstance is true enter a nested loop to swap the factors till the present day detail is at its accurate role.
Step 4: Inside the nested loop swap the elements in arr[] by assigning arr[i] to arr[index[i]] and arr[index[i]] to arr[i].
Step 5: In the equal way swap the factors in index[] by assigning index[i] to index[index[i]] and index[index[i]] to index[i].
Step 6: Repeat the swapping process until the current element is at its correct position.
Step 7: Once the nested loop completes continue with the next iteration of the outer loop.
Step 8: After all iterations, the arr[] and index[] arrays will be reordered according to the given indexes.
FileName: SortedReorder.java
import java.util.*;
class SortedReorder
{
static void reorder(int[] arr,int[] index)
{
int n=arr.length;
for (int i=0;i
{
// Check if the current element is already at its correct position
while (index[i]!=i )
{
// Swap elements in arr[]
int tempElement=arr[index[i]];
arr[index[i]]=arr[i];
arr[i]=tempElement;
// Swap elements in index[]
int tempIndex=index[index[i]];
index[index[i]]=index[i];
index[i]=tempIndex;
}
}
}
public static void main(String[] args)
{
// Example 1
int[] arr1 = {5,8,3,1,9};
int[] index1 = {4,0,3,2,1};
reorder(arr1,index1);
System.out.print("arr[] = ");
for (int element:arr1)
{
System.out.print(element+" ");
}
System.out.print("
index[] = ");
for (int element:index1)
{
System.out.print(element+" ");
}
System.out.println();
// Example 2
int[] arr2 = {2,7,4,6,3};
int[] index2 = {2,4,1,0,3};
reorder(arr2,index2);
System.out.print("arr[] = ");
for (int element:arr2)
{
System.out.print(element+" ");
}
System.out.print("
index[] = ");
for (int element:index2)
{
System.out.print(element+" ");
}
}
}
Output:
arr[] = 8 9 1 3 5 index[] = 0 1 2 3 4 arr[] = 6 4 2 3 7 index[] = 0 1 2 3 4
Complexity Analysis:
Time complexity: The time complexity of this algorithm is O(n), where n is the length of the arrays arr[] and index[], as we iterate through the arrays once to perform the necessary swaps.
Space complexity: The space complexity is O(1) since we do not use any additional data structures that grow with the input size.
Approach3: Using HeapSort algorithm
ALGORITHM:
Step 1: Start with the heapify method, which takes the arr and index arrays, along with an index i.
Step 2: Set the initial largest index as i.
Step 3: Calculate the indices of the left child and right child in 0-based indexing.
Step 4: Compare the values at the left and right children with the value at the largest index. Update the largest index if necessary.
Step 5: If the largest index is not equal to i, swap the elements in both the arr and index arrays.
Step 6: Recursively call heapify on the subtree rooted at the new largest index.
Step 7: Implement the heapSort method, which takes the arr, index, and n (array length) as parameters.
Step 8: Build the initial heap by calling heapify on each parent node, starting from the last parent down to the first.
Step 9: Perform the heap sort by repeatedly swapping the largest element at the root (index 0) with the last element, reducing the heap size, and calling heapify to maintain the heap property.
Step 10: In the main method:
Step 10.1: Define the example arrays arr1, index1, arr2, and index2.
Step 10.2: Calculate the length of each array.
Step 10.3: Set the heapSize to the length of the respective array.
Step 10.4: Call heapSort for each example to reorder the arrays according to the indices.
Step 11: Print the reordered arr arrays and the modified index arrays.
FileName: SortedReorder.java
import java.util.*;
class SortedReorder
{
static int heapSize;
public static 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 0-based indexing
int right = 2 * i + 2;
// Find the largest index from the 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
int temp = arr[largest];
arr[largest] = arr[i];
arr[i] = temp;
temp = index[largest];
index[largest] = index[i];
index[i] = temp;
heapify(arr, index, largest);
}
}
public static 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--)
{
int temp=index[0];
index[0]=index[i];
index[i]=temp;
// Swap arr whenever index is swapped
temp=arr[0];
arr[0]=arr[i];
arr[i]=temp;
heapSize--;
heapify(arr,index,0);
}
}
public static void main(String[] args) {
// Example 1
int[] arr1 = {5, 8, 3, 1, 9};
int[] index1 = {4, 0, 3, 2, 1};
int n1 = arr1.length;
heapSize = n1;
heapSort(arr1, index1, n1);
System.out.print("arr[] = ");
for (int element : arr1) {
System.out.print(element + " ");
}
System.out.print("
index[] = ");
for (int element : index1) {
System.out.print(element + " ");
}
System.out.println();
// Example 2
int[] arr2 = {2, 7, 4, 6, 3};
int[] index2 = {2, 4, 1, 0, 3};
int n2 = arr2.length;
heapSize = n2;
heapSort(arr2, index2, n2);
System.out.print("arr[] = ");
for (int element : arr2) {
System.out.print(element + " ");
}
System.out.print("
index[] = ");
for (int element : index2) {
System.out.print(element + " ");
}
}
}
Output:
arr[] = 8 9 1 3 5 index[] = 0 1 2 3 4 arr[] = 6 4 2 3 7 index[] = 0 1 2 3 4
Complexity Analysis:
Time Complexity: The algorithm has a time complexity of O(n log n) since it utilizes the heap sort algorithm.
Space Complexity: The space complexity is O(1) since it does not require any additional space proportional to the input size.