Sort and rearrange (distinct) arrays

Question

I have two int[] arrays I and J as follows:

int[] I = { 1, 2, 4, 5, 3 };
int[] J = { 8, 7, 6, 3, 2 };

I want to sort I, and then rearrange J using the same indices so the two arrays stay in registration. The result should be:

I = { 1, 2, 3, 4, 5 };
J = { 8, 7, 2, 6, 3 };

Answer 1

This can also be accomplished with Java 8 IntStream and additional Pair class representing a 2-tuple (I know, it's a bit ugly because we have to copy the values back to the array):

public class Main {

    public static void main(String[] args) {

        final int[] I = {1, 2, 4, 5, 3};
        final int[] J = {8, 7, 6, 3, 2};

        List<Pair> pairs = IntStream.range(0, I.length)
                .mapToObj(n -> new Pair(I[n], J[n]))
                .sorted((p1, p2) -> p1.i - p2.i)
                .collect(Collectors.toList());

        for (int k=0; k < pairs.size(); k++) {
            Pair p = pairs.get(k);
            I[k] = p.i;
            J[k] = p.j;
        }

        System.out.println(Arrays.toString(I));
        System.out.println(Arrays.toString(J));
    }

    public static class Pair {
        public int i,j;

        public Pair(int i, int j) {
            this.i = i;
            this.j = j;
        }
    }
}

Output:

[1, 2, 3, 4, 5]
[8, 7, 2, 6, 3]

Keeping the arrays in sync isn't very pretty, I would strongly suggest to model this properly by using an array of tuple objects instead. Then, it's much simpler:

public class Main {

    public static void main(String[] args) {

        final Pair[] P = {new Pair(1,8), new Pair(2,7), new Pair(4,6),
                          new Pair(5,3), new Pair(3,2)};

        Arrays.sort(P, (p1, p2) -> p1.i - p2.i);
        System.out.println(Arrays.toString(P));
    }

    public static class Pair {
        public int i,j;

        public Pair(int i, int j) {
            this.i = i;
            this.j = j;
        }

        @Override
        public String toString() {
            return String.format("(%d, %d)", i, j);
        }
    }
}

Output:

[(1, 8), (2, 7), (3, 2), (4, 6), (5, 3)]

Answer 2

As @ajb has noted in the comments above, the easiest way to implement this is to use a class modelling a tuple.

This has the advantage that you can use the Arrays.sort builtin which saves you from writing your own sorting algorithm. On the other hand, there is the additional overhead of transferring data from the Tuples to the raw arrays.

However, you may find that in your application you are able to directly use the Tuple objects without transferring them back to arrays.

import java.util.*;

class Tuple implements Comparable<Tuple>
{
    int x;
    int y;
    Tuple(int a, int b)
    {
        x = a;
        y = b;
    }

    public int compareTo(Tuple another)
    {
        return Integer.compare(x, another.x);
    }
}

class Main
{
    public static void main(String args[])
    {
        int a[] = {1, 2, 4, 5, 3};
        int b[] = {8, 7, 6, 3, 2};
        Tuple arr[] = new Tuple[a.length];
        for (int i=0;i<a.length;i++)
            arr[i] = new Tuple(a[i], b[i]);
        Arrays.sort(arr);
        for (int i=0;i<a.length;i++)
        {
            a[i] = arr[i].x;
            b[i] = arr[i].y;
        }

        System.out.println(Arrays.toString(a));
        System.out.println(Arrays.toString(b));
    }
}

And the output:

[1, 2, 3, 4, 5]
[8, 7, 2, 6, 3]

Answer 3

I would start by writing a routine to swap elements in an int[]. Something like,

public static void swap(int[] arr, int i, int j) {
    if (i == j) {
        return;
    }
    int t = arr[i];
    arr[i] = arr[j];
    arr[j] = t;
}

Then you could use it and Arrays.toString(int[]) and something like

public static void main(String[] args) {
    int[] I = { 1, 2, 4, 5, 3 };
    int[] J = { 8, 7, 6, 3, 2 };
    for (int i = 0; i < I.length - 1; i++) {
        for (int j = i + 1; j < I.length; j++) {
            if (I[i] > I[j]) {
                swap(I, i, j);
                swap(J, i, j);
            }
        }
    }
    System.out.printf("I = %s%n", Arrays.toString(I));
    System.out.printf("J = %s%n", Arrays.toString(J));
}

Output is (as requested)

I = [1, 2, 3, 4, 5]
J = [8, 7, 2, 6, 3]