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)]));

Not really sure what you are asking, but why not simply `for (int idx : indexes) { ... A[idx] ... B[idx] ...}` — Henry, Nov 29 '18 at 10:03
Do you have duplicates in `indexOrder` or is `indexOrder` sparse? — ernest_k, Nov 29 '18 at 10:18
Thanks for the comments. I have updated the expected input and output. Hope it's more clear now. — chakwok, Nov 29 '18 at 10:19
No, there is not duplicates in indexOrder. Its values are just 0, 1, 2, 3... indexes.length. — chakwok, Nov 29 '18 at 10:21
@DodgyCodeException Yes, the three arrays are of same length. — chakwok, Nov 29 '18 at 11:16
I think Eran gave the right answer (possibly the others too, but I haven't looked at them). However, I would use an array rather than an ArrayList in this case. An `ArrayList` takes up more than 3 times the space of `int[]`, and doesn't give any advantage at all in terms of increased readability to compensate for the extra space & time. — DodgyCodeException, Nov 29 '18 at 12:39
@Andyk.I've updated with a fast solution based on QuickSort algorithm — Anthony Raymond, Nov 29 '18 at 13:42

Eran · Accepted Answer · 2018-11-29T10:33:40.387

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)]));

Anthony Raymond · Answer 2 · 2018-12-03T20:41:27.760

3

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.

edited Dec 03 '18 at 20:41

answered Nov 29 '18 at 10:41

Anthony Raymond

7,434
6
42
59

Thank you for the detailed answer. I realized that my example of indexes array was making a confusion that indexes can be used directly for sorting but it's not the case. – chakwok Nov 29 '18 at 10:52
Ow indeed. Are the numbers known to be in a short interval or it can be the whole Interger range? – Anthony Raymond Nov 29 '18 at 10:56
The range of the numbers is as follows. `0 < indexes[i] <= 1000` – chakwok Nov 29 '18 at 11:02
@Andyk.I've updated my answer according to this constraint – Anthony Raymond Nov 29 '18 at 13:41
Love how you approached the question. Thanks for sharing. – chakwok Nov 30 '18 at 08:25
1

I see how this works and should be quite fast. By the way, a possible way to get the max index value more consisely (and probably more readable): `final int maxIndexValue = IntStream.of(indexes).max().getAsInt();` – DodgyCodeException Nov 30 '18 at 09:33
@DodgyCodeException Yes indeed, i added it to the example along with a warning about the fact that i cost more time to perform that a regular for loop. It's sad that streams are slower than regular loops... So i try to use them only when the readability is greatly improved. – Anthony Raymond Nov 30 '18 at 09:50
Indeed, stream operations are slower than raw loops over primitive arrays. However, the JIT can make this difference minimal; and if the relevant piece of code isn't JITed it's because it hasn't been run enough times to make much difference anyway. In [Angelika Langer's study](https://jaxenter.com/java-performance-tutorial-how-fast-are-the-java-8-streams-118830.html) stream operations took 15 times longer than raw loops over an array of int, but this was without a warm-up (i.e. no JIT). So in such a case, what difference does 15 microseconds vs 1 microsecond make? Both are blindingly fast. – DodgyCodeException Nov 30 '18 at 13:28
@DodgyCodeException Yep, probably not a big deal for such small sets of data. – Anthony Raymond Nov 30 '18 at 14:19
In fact, once the Stream operations get JITed, using Streams appears to be FASTER than using loops! See https://ideone.com/Qnwo8j – DodgyCodeException Nov 30 '18 at 14:31
Wow, impressive, didn't knew that it scale that much with JIT. Good to know :) – Anthony Raymond Nov 30 '18 at 15:01
1

I think your algorithm is a variant of [Counting Sort](https://en.wikipedia.org/wiki/Counting_sort) with the count being either 0 or 1 (since there are no duplicates). – DodgyCodeException Dec 03 '18 at 14:14
That's it ! I could not remember the name. Thanks :) – Anthony Raymond Dec 03 '18 at 20:41

score 0 · Answer 3 · answered Nov 29 '18 at 10:56

I tried to ran both the code and I get the same result in both the cases.

Case 1 :

public static void main(String[] args) {
    String[] A = { "a", "b", "c", "d" };
    String[] B = { "e", "f", "g", "h" };
    int[] indexes = { 0, 4, 2, 1 };

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

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

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

    System.out.println(indexOrder.toString());
}

Ouput : 0 1 2 3

[0, 3, 2, 1]

Case 2:

public static void main(String[] args) {
    String[] A = { "a", "b", "c", "d" };
    String[] B = { "e", "f", "g", "h" };
    int[] indexes = { 0, 4, 2, 1 };

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

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

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

    System.out.println(indexOrder.toString());
}

output : 0 1 2 3

[0, 3, 2, 1]

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

3 Answers3

Related