Preserve indices while sorting array

Introduction

This is a request from one of the readers. This is mostly useful in competitive programming where you want to sort an array by the values, but at the same time the requirement is to preserve the index of each element.

If I have to explain using an example, then consider the array below. The array is zero indexed.

Preserve indices while sorting array

The first two rows represent the input array and indices of each element in the array. The next two rows represent the sorted array, but the moment you sort it, the index for each element changes. Earlier A was at index 4 but in the sorted array it is at index zero.

The output expected from the program is represented in the last row. Instead of printing the elements in the sorted array, print their original indices after they are sorted.

Solution to Preserve indices while sorting array

The idea here is to preserve the index and hence we would prefer to sort the index array instead of sorting the actual array. In Java way of doing it, we can write a Comparator  like below:

In this Comparator, we preserve the actual array which is to be sorted. Also, if you notice, the compare method compares the values of the actual array based on the indices supplied to it. The key here is to supply the indices and not the actual values to be sorted.

Here is how you will invoke this Comparator:

S is the character array to be sorted, indexArray is an auxiliary array we will sort upon. Before sorting, the index array will contain numbers in a sequence 0 – length of the array to be sorted. When we invoke the Arrays.sort method on the index array, it passes the two indices to the compare method and compares the values stored at those indices.