Sorting pairs or more of ints. Is there a better way than arrays?

Question

I'm wondering if there is a better way to do this, work with pairs of numbers. I'm working through the problems on CodeAbbey. This one was

sort these numbers, then print out their original index location.

I did it like this. ( I'm still learning. )

public static void bSort(int[][] a) {
    boolean sorted = false;
    int temp;
    int temp2;

    while (!sorted) {
        int counter = 0;

        for (int i = 0; i < a.length - 1; i++) {
            if (a[i][0] > a[i + 1][0]) {
                temp = a[i][0];
                temp2 = a[i][1];
                a[i][0] = a[i + 1][0];
                a[i + 1][0] = temp;

                a[i][1] = a[i + 1][1];
                a[i + 1][1] = temp2;
                counter++;
            }
        }
        if (counter == 0) {
            sorted = true;
        }
    }
    for (int i = 0; i < a.length; i++) {
            System.out.print(a[i][1] + " ");
    }
}

I kept running into this as I was searching: Sort a Map<Key, Value> by values (Java) but I haven't worked with maps yet.

Answer 1

You can create a class holding a pair of ints :

class Pair implements Comparable<Pair>{

    int number, index;

    @Override
    public int compareTo(Pair other){
        return Integer.compare(number, other.number);
    }
}

Then you can sort an array of Pair like this :

Pair[] pairs = new Pair[]; // initialize with values
Arrays.sort(pairs);

This will sort an array or Pair according to number and if you iterate over it afterwards you can get the index of each Pair

Alternatively you can implement the Comparator interface outside the Pair class

class PairComparator implements Comparator<Pair> {
    @Override
    public int compare(Pair a, Pair b) {
        return Integer.compare(a.number, b.number);
    }
}

and use it like this

Arrays.sort(pairs, new PairComparator());

Answer 2

There are lots of ways to solve any given problem. While it might seem a bit to take in early in your learning curve I suggest you get used to Java 8 streams and lambdas. Once you are used to them you'll find them a natural way of solving lots of problems.

So here's a stream based solution to your problem which I'll then explain:

void printSortedIndexes(int[] list) {
    IntStream.range(0, list.length).boxed()
        .sorted(Comparator.comparingInt(n -> list[n]))
        .forEach(System.out::println);
}

This can be interpreted as: make a stream of integers from 0 to the length of the list - 1, convert to a stream of Integer objects, sort them by comparing the integers at that index in the list and then print them out. I think that's a better way than storing the index and manually sorting them.

Answer 3

It at least is probably better than two parallel arrays of same length. "Probably" because a[indices[i]] - the permutation approach -, is a fine solution too.

Other answers already mention some approaches.

Your approach would more consequently use the pair int[]:

public static void bSort(int[][] a) {
    boolean sorted = false;
    int fromI = 0;
    while (!sorted) {
        boolean changed = false;
        for (int i = fromI; i < a.length - 1; i++) {
            int[] current = a[i];
            int[] next = a[i + 1];
            if (current[0] > next[0]) {
                int temp = current[0];
                int temp2 = current[1];
                current[0] = next[0];
                current[1] = next[1];
                next[0] = temp;
                next[1] = temp2;
                if (!changed) {
                    fromI = i;
                    changed = true;
                }
            }
        }
        if (!changed) {
            sorted = true;
        }
    }
    for (int[] current : a) {
        System.out.print(current[1] + " ");
    }
}

In the above:

• There is no penalty for declaring a variable in a loop, entirely identical.
• One could use System.arrayCopy.
• temp/temp2 could be one int[] too, but then better created outside the loop.

Answer 4

Here is a solution using Maps

Map<Integer, Integer> toBeSorted = new HashMap<>();

toBeSorted.put(1, -2);
toBeSorted.put(2, -1);
toBeSorted.put(3, 8);
toBeSorted.put(4, 7);
toBeSorted.put(5, 6);
toBeSorted.put(6, 500);
toBeSorted.put(7, 4);
toBeSorted.put(8, 3);
toBeSorted.put(9, 2);
toBeSorted.put(10, 1);

final Comparator<Map.Entry<Integer, Integer>> comparator =

    new Comparator<Map.Entry<Integer, Integer>>() {

  @Override
  public int compare(Map.Entry<Integer, Integer> o1,
                     Map.Entry<Integer, Integer> o2) {
    return o1.getValue().compareTo(o2.getValue());
  }

};//Comparator

//need a List to keep contract with Collections.sort()
final List<Map.Entry<Integer, Integer>> list =
    new ArrayList<>(toBeSorted.entrySet());

//invoke sort 
Collections.sort(list, comparator);

for(Map.Entry<Integer, Integer> entry : list) {
  System.out.println(entry.getKey() + " -> " + entry.getValue());
}

prints out:

1 -> -2
2 -> -1
10 -> 1
9 -> 2
8 -> 3
7 -> 4
5 -> 6
4 -> 7
3 -> 8
6 -> 500