Sort array in JAVA and then return the index of elements in sorted order

Sort a list in JAVA and then return the index of elements in sorted order.

Examples:

Input  : [2, 3, 1, 4, 5]  
Output : [2, 0, 1, 3, 4]
After sorting list becomes [1, 2, 3, 4, 5]  
and their index as [2, 0, 1, 3, 4]

Input  : [6, 4, 7, 8, 1]
Output : [4, 1, 0, 2, 3]
After sorting the list becomes [1, 4, 6, 7, 8]  
and their index as [4, 1, 0, 2, 3].

Approach :

Make pair (element,index) of elements of the array with their initial indices.
Sort the pair array using comparator based on the first value (element’s value) in increasing order.
Return the indices of the elements after sorting using a loop.

Below is the impletation of the above approach:

// JAVA code of the above approach
import java.util.*;
public class Cpp {
  // A class of pair consisting of element,index
  static class Pair {
    int ele;
    int ind;
    Pair(int ele, int ind) {
      this.ele = ele;
      this.ind = ind;
    }
  }
  // Function that prints the index of the array elements after sorting
  static void index_sort(int a[], int n) {
    // Pair array consists of element,index pair for each array elements
    Pair p[] = new Pair[n];
    for (int i = 0; i < n; i++) {
      p[i] = new Pair(a[i], i);
    }

    // Sort using Comparator based on the element i.e first value of pair
    Arrays.sort(p, new Comparator < Pair > () {
      @Override
      public int compare(Pair p1, Pair p2) {
        return p1.ele - p2.ele;
      }
    });

    // Print the indices after sorting
    for (int i = 0; i < n; i++) {
      System.out.print(p[i].ind + " ");
    }

  }
  
  // Driver Code
  public static void main(String args[]) {
    // Given array
    int a[] = {2, 3, 1, 4, 5};
    int n = a.length;

    // Function Call
    index_sort(a, n);
  }
}

Output:

2 0 1 3 4

Time Complexity : O(nlogn)
Space Complexity : O(n)

Please write comments below if you find anything incorrect, or you want to share more information about the topic discussed above. A gentle request to share this topic on your social media profile.