8

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)]));
Improve this question
9
  • what is your input and expected output? Commented Nov 29, 2018 at 10:03
  • 3
    Not really sure what you are asking, but why not simply for (int idx : indexes) { ... A[idx] ... B[idx] ...} Commented Nov 29, 2018 at 10:03
  • Do you have duplicates in indexOrder or is indexOrder sparse? Commented Nov 29, 2018 at 10:18
  • Thanks for the comments. I have updated the expected input and output. Hope it's more clear now. Commented Nov 29, 2018 at 10:19
  • No, there is not duplicates in indexOrder. Its values are just 0, 1, 2, 3... indexes.length. Commented Nov 29, 2018 at 10:21

3 Answers 3

Reset to default
6

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)]));
Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

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.

Improve this answer

13 Comments

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.
Ow indeed. Are the numbers known to be in a short interval or it can be the whole Interger range?
The range of the numbers is as follows. 0 < indexes[i] <= 1000
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();
I think your algorithm is a variant of Counting Sort with the count being either 0 or 1 (since there are no duplicates).
|
0

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]

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.