Sorting matched arrays in Java

Question

Let's say that I have two arrays (in Java),

int[] numbers; and int[] colors;

Each ith element of numbers corresponds to its ith element in colors. Ex, numbers = {4,2,1} colors = {0x11, 0x24, 0x01}; Means that number 4 is color 0x11, number 2 is 0x24, etc.

I want to sort the numbers array, but then still have it so each element matches up with its pair in colors.

Ex. numbers = {1,2,4}; colors = {0x01,0x24,0x11};

What's the cleanest, simplest way to do this? The arrays have a few thousand items, so being in place would be best, but not required. Would it make sense to do an Arrays.sort() and a custom comparator? Using library functions as much as possible is preferable.

Note: I know the "best" solution is to make a class for the two elements and use a custom comparator. This question is meant to ask people for the quickest way to code this. Imagine being at a programming competition, you wouldn't want to be making all these extra classes, anonymous classes for the comparator, etc. Better yet, forget Java; how would you code it in C?

Answer 1

You need to sort the colors array by its relative item in the numbers array. Specify a comparator that compares numbers and use that as the comparison for the colors array.

Answer 2

Why not introduce an object to represent a number and a color and implement a comparator function for that?

Also, do you really need an array, why not use something derived from Collection?

Answer 3

It seems like the cleanest thing to do would be to create a custom property class that implements Comparable. For example:

class Color implements Comparable {
  private int number;
  private int color;

  // (snip ctor, setters, etc.)

  public int getNumber() {
    return number;
  }
  public int getColor() {
    return color;
  }

  public int compareTo(Color other) {
    if (this.getNumber() == other.getNumber) {
      return 0;
    } else if (this.getNumber() > other.getNumber) {
      return 1;
    } else {
      return -1;
    }
  }
}

Then you can separate your sorting algorithm from the ordering logic (you could use Collections.sort if you use a List instead of an array), and most importantly, you won't have to worry about somehow getting two arrays out of sync.

Answer 4

If you'd be willing to allocate some extra space, you could generate another array, call it extra, with elements like this:

extra = [0,1,...,numbers.length-1]

Then you could sort this extra array using Arrays.sort() with custom comparator (that, while comparing elements i and j really compares numbers[extra[i]] and numbers[extra[j]]). This way after sorting the extra array, extra[0] would contain the index of the smallest number and, as numbers and colours didn't move, the corresponding colour.
This isn't very nice, but it gets the job done, and I can't really think of an easier way to do it.

As a side note, in the competition I usually find the C++ templated pairs and nice maps indispensable ;)

Answer 5

You could use sort() with a custom comparator if you kept a third array with the index, and sorted on that, leaving the data intact.

Answer 6

I like @tovare's solution. Make a pointer array:

int ptr[] = { 1, 2, 3 };

and then when you sort on numbers, swap the values in ptr instead of in numbers. Then access through the ptr array, like

for (int i = 0; i < ptr.length; i++)
{
   printf("%d %d\n", numbers[ptr[i]], colors[ptr[i]]);
}

Update: ok, it appears others have beaten me to this. No XP for me.

Answer 7

Would it suffice to code your own sort method? A simple bubblesort would probably be quick to code (and get right). No need for extra classes or comparators.

Answer 8

One quick hack would be to combine the two arrays with bit shifts. Make an array of longs such that the most significant 32 bits is the number and the least significant 32 is the color. Use a sorting method and then unpack.

Answer 9

The simplest way to do this in C, would be bubblesort + dual pointers. Ofcourse the fastest would be quicksort + two pointers. Ofcourse the 2nd pointer maintains the correlation between the two arrays.

I would rather define values that are stored in two arrays as a struct, and use the struct in a single array. Then use quicksort on it. you can write a generic version of sort, by calling a compare function, which can then be written for each struct, but then you already know that :)

Answer 10

Use a TreeMap