Java: Sorting an array based on another array with indexOf method

Question

I want to iterate through two arrays(A, B) based on the sorted order of another array(indexes), which is 10, 34, 32, 21 in this case.

String[] A: a, b, c, d
String[] B: e, f, g, h
int[] indexes: 10, 34, 32, 21

Apology for the bad example here. I have updated the indexes array to clear the confusion.

Expected Input and Output

The input are the three arrays. I wanted to iterate through A, B using the sorted of the indexes array. i.e. I want to find a way to iterate A using the order (a, d, c, b) and iterate B using the order (e, h, g, f)

My approach:

I solved the problem with a solution that I believe is identical to another approach. However, the second approach does not work. I would appreciate if someone can explain why it does not work as I think it would give me a better understanding of how Collections.sort works in java.

List<Integer> indexOrder = new ArrayList<>(indexes.length);

for (int i = 0; i < indexes.length; i++) {
    indexOrder.add(i);
}

Collections.sort(indexOrder, Comparator.comparing((Integer s) -> indexes[s]));

Inspired by this thread, I created an ArrayList (prefer AList not array) with value (1, 2, 3...indexes.length) and then sort it using a comparator with ref. to indexes. The codes above work as expected.

However, if I change the indexes[s] at the end of the last line to indexes[indexOrder.indexOf(s)]. The sorting will give a wrong result. Why is indexOf(s) giving a different result than s if the ArrayList's index is the same as its value.

Collections.sort(indexOrder, Comparator.comparing((Integer s) -> indexes[indexOrder.indexOf(s)]));

Answer 1

It seems you expect indexOrder.indexOf(s) to always be equal to s (since your List was initialized to [0, 1, 2, 3], where the index of s is s).

While this is true in your original indexOrder List, this may no longer true when Collections.sort starts swapping elements of your List.

In order not to rely on the ordering of indexOrder while you are sorting it, you can create a copy of that List:

List<Integer> copy = new ArrayList<>(indexOrder);
Collections.sort(indexOrder, Comparator.comparing((Integer s) -> indexes[copy.indexOf(s)]));

Answer 2

Since the maximum value stored in indexes won't exceed 1000 i feel like an implementation of this sorting algorithm (which is a variant of the counting sort) will be the best choice.

final String[] A = { "a", "b", "c", "d" };
final String[] B = { "e", "f", "g", "h" };
final int[] indexes =  { 10, 34, 32, 21 };

// find out the max value in the array.
// The loop can be skipped with maxIndexValue = 1000; but i would most likely save some memory using the loop.
// Can also be replaced with : IntStream.of(indexes).max().getAsInt(), with such a small set of data it won't hurt performance that bad
int maxIndexValue = 0;
for (int indexValue: indexes) {
    if (maxIndexValue < indexValue) {
        maxIndexValue = indexValue;
    }
}
maxIndexValue += 1;

final String[] indexSortedA = new String[maxIndexValue];
final String[] indexSortedB = new String[maxIndexValue];
System.out.println(maxIndexValue);
// each value of A (and B) will be put at indexes position, it will result in a appropriately sorted arrays but with a lot of whitespace.
for (int i = 0; i < indexes.length; ++i) {
    indexSortedA[indexes[i]] = A[i];
    indexSortedB[indexes[i]] = B[i];
}

// Create final arrays by filtering empty values
final String[] sortedA = Arrays.stream(indexSortedA).filter(v -> v != null && !"".equals(v)).toArray(String[]::new);
final String[] sortedB = Arrays.stream(indexSortedB).filter(v -> v != null && !"".equals(v)).toArray(String[]::new);

Complexity of this algorithm will be : O(n) + O(1000) + O(2n). It will be better nthan any Collection.sort() but it cost a bit more memory.