Sorting the Indexes of an Array
Articles —> Sorting the Indexes of an Array
In Java, sorting an array or List is often as simple as using the Arrays or Collection utility classes, respectively. However there may be times when one wishes to find the indexes of the sorted array, for instance if one does not wish to actually sort the array or List (eg it may be shared across clients), or alternatively the indexes may be used as a key or index for another data structure.
To implement this type of behavior one can create a second array containing the indexes, sorting this array based upon the values of the first using a custom Comparator; a Comparator which compares the values of the of the first array in order to sort the second. The following class can be used to accomplish this task, and is a generic version allowing any array or Collection containing comparable elements to be sorted:
/** * Class to sort the indexes of an array based upon their values. Note the array or Collection passed * into the constructor is not itself sorted. * doubles, * @author G, Cope * */ public class IndexSorter<T extends Comparable<T>> implements Comparator<Integer>{ private final T[] values; private final Integer[] indexes; /** * Constructs a new IndexSorter based upon the parameter array. * @param d */ public IndexSorter(T[] d){ this.values = d; indexes = new Integer[this.values.length]; for ( int i = 0; i < indexes.length; i++ ){ indexes[i] = i; } } /** * Constructs a new IndexSorter based upon the parameter List. * @param d */ public IndexSorter(List<T> d){ this.values = (T[])d.toArray(); for ( int i = 0; i < values.length; i++ ){ values[i] = d.get(i); } indexes = new Integer[this.values.length]; for ( int i = 0; i < indexes.length; i++ ){ indexes[i] = i; } } /** * Sorts the underlying index array based upon the values provided in the constructor. The underlying value array is not sorted. */ public void sort(){ Arrays.sort(indexes, this); } /** * Retrieves the indexes of the array. The returned array is sorted if this object has been sorted. * @return The array of indexes. */ public Integer[] getIndexes(){ return indexes; } /** * Compares the two values at index arg0 and arg0 * @param arg0 The first index * @param arg1 The second index * @return The result of calling compareTo on T objects at position arg0 and arg1 */ @Override public int compare(Integer arg0, Integer arg1) { T d1 = values[arg0]; T d2 = values[arg1]; return d1.compareTo(d2); } }
The above class implements the Comparator interface, and calling its sort method sorts its index array based upon the value array. Note the underlying data structure passed to the constructor is not sorted, however retrieving the index array from the IndexSorter allows one to access the values of the underlying array or Collection in a sorted way. A simple example of the usage follows:
public static void main(String[] args){ Integer[] integers = new Integer[]{1,100, 95, 2, -10, -5}; IndexSorter<Integer> is = new IndexSorter<Integer>(integers); is.sort(); System.out.print("Unsorted: "); for ( Integer i : integers ){ System.out.print(i); System.out.print("\t"); } System.out.println(); System.out.print("Sorted"); for ( Integer i : is.getIndexes() ){ System.out.print(integers[i]); System.out.print("\t"); } System.out.println(); }
The above code simply creates an array of Integers, then sorts the indexes of the array using the IndexSorter class. Note that the array itself is not sorted, but can be accessed in a sorted way via the values of the getIndexes() method of the IndexSorter class.
Comments
- Waqar Detho - August, 25, 2015
Thank you so much. It is very easy code and works perfectly fine.