Sorting Arrays in Java (with Their Indices)

You can download the project built in this tutorial by clicking HERE.
You can download the SortArray_1.0.jar API and the JavaDoc by clicking HERE.

Anyone who has studied (or is studying) computer engineering has run into array sorting methods in some course (in my case it was "Algorithmics and Complexity"). It seems like something trivial, but it’s not so trivial when you have to sort arrays of a considerable size, since array sorting algorithms have O(n^2) complexity.

To give a quick summary of array sorting methods (without going into the details), these methods fall into 3 types: 1.- Insertion methods, 2.- Selection methods and 3.- Exchange methods. Insertion methods include direct insertion(*) and binary insertion. Among the selection methods there is direct selection, and among the exchange methods we find bubble sort, shaker sort and quickSort(*). After many years of listening to people, they only remember bubble sort (I guess because of its peculiar name), but it has to be said that of all the methods mentioned, it is by far the worst one for sorting arrays. The methods marked with (*) are the most recommended ones for sorting arrays: direct insertion and quickSort.

Getting to what we care about, in Java we have the "sort" method of the Arrays class, which sorts an array from lowest to highest. I’m not sure, but judging by the name it "looks like" it uses quickSort. Let’s see an example of how to call this method:

// Array to sort:
int[] intArray = { 3, 2, 8, 5, 7, 9 };
// "sort" method to sort the array
Arrays.sort(intArray);

If you run a Java program with this code and print the array after calling this method, you’ll see that it gives you the array sorted from lowest to highest.

As you can see, it’s very easy to sort an array of any data type from lowest to highest, but: what if I want to sort it from highest to lowest? Or what if I want to know the indices of the array after sorting? In other words, how do I solve the following problem:

...Array desordenado de enteros ...
Indices: 0 1 2 3 4 5 
Array:   3 2 8 5 7 9 
...Array Ordenado decrecientemente con sus indices ...
Indices: 5 2 4 3 0 1 
Array:   9 8 7 5 3 2

Well, relax, it’s not the end of the world ;). For the experiments I usually do, I often need to get, given an array, its sorted array along with its indices. I found many solutions on the web, such as "StackOverflow", but in the end none of them convinced me, so I decided to build an API that solves these problems for arrays of ints, floats, doubles and Strings. I called this API SortArray and you can download it from the link I put above. The ".jar" is called "SortArray_1.0.jar". With this API you can sort arrays of the data types mentioned above, from highest to lowest or from lowest to highest, and you can get the indices of the arrays after sorting. Below are examples of how to use the API, which are the same ones you can find in the project.

Given an array of integers "intArray", I want to sort it from lowest to highest and from highest to lowest, knowing the indices. To do that, I create an object of the "SortArray" class and call the sorting methods, then ask for the corresponding arrays with the "get" methods:

// Array to sort:
int[] intArray = { 3, 2, 8, 5, 7, 9 };
int[] intArray2 = Arrays.copyOf(intArray, intArray.length); // I make a copy of the array to sort it from highest to lowest
// We sort the array from lowest to highest
SortArrays sortArrays = new SortArrays(intArray);  // We create an object of the SortArray class
sortArrays = sortArrays.increasingOrderInt();      // We call the method that sorts the array and its indices from lowest to highest
int [] indices = sortArrays.getIndexArray();       // I get the array indices after sorting
int [] arrayOrdenado = sortArrays.getIntArray();   // I get the sorted integer array 

// We sort the array from highest to lowest
sortArrays = new SortArrays(intArray2);           // We create the object of the SortArray class
sortArrays = sortArrays.decreasingOrderInt();     // We call the method that sorts the array from highest to lowest
int indices [] = sortArrays.getIndexArray();      // I get the array indices after sorting
int [] arrayOrdenado = sortArrays.getIntArray();  // I get the sorted integer array

This code doesn’t work as is, because it’s pseudocode. In the project you can download, it’s written correctly. Here I wrote it this way so it’s easy to understand and read. If you run the project, you’ll see that it returns the sorted arrays with their respective indices. If you print these arrays on screen, you’ll get the following:

...Array desordenado de enteros ...
Indices: 0 1 2 3 4 5 
Array:   3 2 8 5 7 9 
...Array Ordenado crecientemente con sus indices utilizando el API ...
Indices: 1 0 3 4 2 5 
Array:   2 3 5 7 8 9 

...Array desordenado de enteros ...
Indices: 0 1 2 3 4 5 
Array:   3 2 8 5 7 9 
...Array Ordenado decrecientemente con sus indices utilizando el API ...
Indices: 5 2 4 3 0 1 
Array:   9 8 7 5 3 2

This case showed how to sort an integer array. To sort arrays of the other types, you have to call the following methods, which you can see in the JavaDoc that you can download from the link above:

// SORT FLOAT ARRAY FROM LOWEST TO HIGHEST
SortArrays sortArrays = new SortArrays(floatArray);	// We create the object, passing the array to the constructor
sortArrays = sortArrays.increasingOrderFloat();		// We call the method to sort the array from lowest to highest
int [] indices = sortArrays.getIndexArray();		// We get the indices of the sorted array
float [] arrayOrdenado = sortArrays.getFloatArray();	// We get the float array sorted from lowest to highest

// SORT FLOAT ARRAY FROM HIGHEST TO LOWEST
SortArrays sortArrays = new SortArrays(floatArray);	// We create the object, passing the array to the constructor
sortArrays = sortArrays.decreasingOrderFloat();		// We call the method to sort the array from highest to lowest
int [] indices = sortArrays.getIndexArray();		// We get the indices of the sorted array
float [] arrayOrdenado = sortArrays.getFloatArray();	// We get the float array sorted from lowest to highest

// SORT DOUBLE ARRAY FROM LOWEST TO HIGHEST
SortArrays sortArrays = new SortArrays(doubleArray);	// We create the object, passing the array to the constructor
sortArrays = sortArrays.increasingOrderDouble();	// We call the method to sort the array from lowest to highest
int [] indices = sortArrays.getIndexArray();		// We get the indices of the sorted array
double [] arrayOrdenado = sortArrays.getDoubleArray();	// We get the double array sorted from lowest to highest

// SORT DOUBLE ARRAY FROM HIGHEST TO LOWEST
SortArrays sortArrays = new SortArrays(doubleArray);	// We create the object, passing the array to the constructor
sortArrays = sortArrays.decreasingOrderDouble();	// We call the method to sort the array from highest to lowest
int [] indices = sortArrays.getIndexArray();		// We get the indices of the sorted array
double [] arrayOrdenado = sortArrays.getDoubleArray();	// We get the double array sorted from highest to lowest

// SORT STRING ARRAY FROM LOWEST TO HIGHEST
SortArrays sortArrays = new SortArrays(stringArray);	// We create the object, passing the array to the constructor
sortArrays = sortArrays.increasingOrderString();	// We call the method to sort the array from lowest to highest
int [] indices = sortArrays.getIndexArray();		// We get the indices of the sorted array
String [] arrayOrdenado = sortArrays.getStringArray();	// We get the string array sorted from lowest to highest

// SORT STRING ARRAY FROM HIGHEST TO LOWEST
SortArrays sortArrays = new SortArrays(stringArray);	// We create the object, passing the array to the constructor
sortArrays = sortArrays.decreasingOrderString();	// We call the method to sort the array from highest to lowest
int [] indices = sortArrays.getIndexArray();		// We get the indices of the sorted array
String [] arrayOrdenado = sortArrays.getStringArray();	// We get the string array sorted from highest to lowest

With these objects and methods, if we want to sort the following arrays:

float[] floatArray = { 3.3f, 2.2f, 8.8f, 5.5f, 7.7f, 9.9f };
double[] doubleArray = { 3.33333, 2.22222, 8.88888, 5.55555, 7.77777, 9.99999 };
String[] stringArray = { "España", "Francia", "Italia",	"Alemania", "Holanda" };

We’ll get the following output (this is what you get by running the project we shared):

...Array desordenado de floats ...
Indices:  0     1     2     3     4     5    
Array:   3.3   2.2   8.8   5.5   7.7   9.9   
...Array Ordenado crecientemente con sus indices utilizando el API ...
Indices:  1     0     3     4     2     5    
Array:   2.2   3.3   5.5   7.7   8.8   9.9   

...Array desordenado de floats ...
Indices:  0     1     2     3     4     5    
Array:   3.3   2.2   8.8   5.5   7.7   9.9   
...Array Ordenado decrecientemente con sus indices utilizando el API ...
Indices:  5     2     4     3     0     1    
Array:   9.9   8.8   7.7   5.5   3.3   2.2   

...Array desordenado de doubles ...
Indices:    0         1         2         3         4         5      
Array:   3.33333   2.22222   8.88888   5.55555   7.77777   9.99999   
...Array Ordenado crecientemente con sus indices utilizando el API ...
Indices:    1         0         3         4         2         5      
Array:   2.22222   3.33333   5.55555   7.77777   8.88888   9.99999   

...Array desordenado de doubles ...
Indices:    0         1         2         3         4         5      
Array:   3.33333   2.22222   8.88888   5.55555   7.77777   9.99999   
...Array Ordenado decrecientemente con sus indices utilizando el API ...
Indices:    5         2         4         3         0         1      
Array:   9.99999   8.88888   7.77777   5.55555   3.33333   2.22222   

...Array desordenado de Strings ...
Indices:    0         1         2         3         4      
Array:   España   Francia   Italia   Alemania   Holanda   
...Array Ordenado crecientemente con sus indices utilizando el API ...
Indices:    3         0         1         4         2      
Array:   Alemania   España   Francia   Holanda   Italia   

...Array desordenado de Strings ...
Indices:    0         1         2         3         4      
Array:   España   Francia   Italia   Alemania   Holanda   
...Array Ordenado decrecientemente con sus indices utilizando el API ...
Indices:    2         4         1         0         3      
Array:   Italia   Holanda   Francia   España   Alemania

Now that we’ve explained how the API works and that you can download it without any problem, let’s explain how we built the methods for sorting arrays and indices. We’ll explain it for the case of sorting an integer array, but by changing the variable types you’d do the same thing for any other data type.

The first thing we do is make a copy of the array we want to sort, so we can later compare them and get the sorted indices of the array. Copying arrays is done like this:

int[] intArray = { 3, 2, 8, 5, 7, 9 };                               // Original array
int[] intArrayCopia = Arrays.copyOf(intArray, intArray.length);      // Copy of the array

BE VERY CAREFUL!!!! when making the copy. Many people confuse making a copy with copying the reference. If you do "intArray=intArrayCopia", you are copying the reference of the array. This is a bit long to explain, but make sure you make the copy properly, because lots of people get this wrong.

Once the array has been copied, we sort the first array from lowest to highest with the "sort" method of the Arrays class, just as we showed at the start of the tutorial:

// Order the Array in increasing order
Arrays.sort(intArray);

In this case we have two arrays: the one sorted from lowest to highest and the unsorted one. If we want the array sorted from highest to lowest, we created the following method, which reverses the order of the array:

public int[] invertIntArray(int[] array) {
	int i = 0;
	int j = array.length - 1;
	int tmp;
	while (j > i) {
		tmp = array[j];
		array[j] = array[i];
		array[i] = tmp;
		j--;
		i++;
	}
	return array;
}

This method is only used if we want to sort the array from highest to lowest.

Now all that’s left is to find the indices of the arrays. That’s why we made a copy of the original array: to compare them and get their indices. The following method gets the order of the indices by taking the unsorted array and the sorted array as parameters:

private int[] orderIntIndex(int[] disorderArray, int[] orderArray) {
	int lon = disorderArray.length;

	int[] index = new int[lon];
	Arrays.fill(index, 0);

	boolean[] esta = new boolean[lon];
	Arrays.fill(esta, false);

	for (int i = 0; i < orderArray.length; i++) {
		int in = 0;
		boolean stay = false;
		while (in < orderArray.length & !stay) {
			if ((disorderArray[in] == orderArray[i]) & !esta[in]) {
				esta[in] = true;
				index[i] = in;
				stay = true;
			} else {
				in++;
			}
		}
	}
	return index;
}

This is how the API was built, obviously changing the data types for each case. That’s all. We made the API ourselves and you can download and share it freely. If you have any comments or questions about the API, leave us a comment on the post ;).