Sort a two dimensional array based on the first column

Question

I have read a lot of stackoverflow-posts and some google-results, but havent found something perfect.

Basically I have a two dimensional array with points(integer) in the first row and an integer to identify which "run" the points belong to. I want to sort the array based on the points, but not lose the identifier when sorting.

What is the shortes way to write that sortcode?

Before:

string points[][] = 
        {
          { 12, 13, 10, 0, 0, 0 },
          { 1, 2, 3, 4, 5, 6 },      
        }

After:

string points[][] = 
        {
          { 13, 12, 10, 0, 0, 0 },
          { 2, 1, 3, 4, 5, 6 },      
        }

Not the best example, but i hope you see the point.

Answer 1

Unfortunately, Java's Collections library lacks methods for sorting "parallel arrays". Create a class to hold your runs, sort it using the class library with a custom comparator, and put the data back into your array:

public class Run {
    public int points;
    public int runId;
}

Run[] runs = new Run[points[0].length];
for (int i = 0 ; i != runs.length ; i++) {
    Run r = new Run();
    r.points = points[0][i];
    r.runId = points[1][i];
    runs[i] = r;
}
Arrays.sort(runs, new Comparator<Run>() {
    public int compare(Run a, Run b) { 
        return -Integer.compare(a.points, b.points);
    }
});
for (int i = 0 ; i != runs.length ; i++) {
    points[0][i] = runs[i].points;
    points[1][i] = runs[i].runId;
}

Demo.

Answer 2

Okay, so normally I would recommend using a sorted map/array list but if that's not an option...

Run through a normal sort algorithm as you would anything else on the first row. However, if you do have to make a swap then just simultaneously swap the second row's value in the same way, e.g.:

//loop through int i

if(points[i][0] < points[i+1][0]){
    int temp = points[i][0];
    points[i][0] = points[i + 1][0];
    points[i+1][0] = temp;

    temp = points[i][1];
    points[i][1] = points[i + 1][1];
    points[i+1][1] = temp;
}

Nice and simple.

Answer 3

Using a simple selection-sort:

public static void test()
{
        Integer points[][] = 
                {
                  { 12, 13, 10, 0, 0, 0 },
                  { 1, 2, 3, 4, 5, 6 },      
                };
        selectionSort(points[0], points[1]);
        System.out.println(Arrays.toString(points[0]));
        System.out.println(Arrays.toString(points[1]));
}

private static void swap(Integer[] arr, Integer[] arr2, int i, int minIndex)
{
    int tmp = arr[i];
    arr[i] = arr[minIndex];
    arr[minIndex] = tmp;

    tmp = arr2[i];
    arr2[i] = arr2[minIndex];
    arr2[minIndex] = tmp;       
}

// Use any sorting algorithm you like, just keep the swap method.
public static void selectionSort(Integer[] arr, Integer[] arr2) 
{
    int i, j, minIndex;
    int n = arr.length;
    for (i = 0; i < n - 1; i++) 
    {
        minIndex = i;

        for (j = i + 1; j < n; j++)
            if (arr[j] > arr[minIndex])
                minIndex = j;

        if (minIndex != i) 
        {
            swap(arr, arr2, i, minIndex);
        }
    }
}

Answer 4

Can you swap the indices, i.e. store the 2x6 array in your example as a 6x2 array instead and index it via points[y][x] rather than points[x][y]?

If so, you can just use the regular sorting functions with a custom comparator that compares the first elements in each sub-array:

Arrays.sort(points, new Comparator<int[]>() {
    @Override
    public int compare(int[] o1, int[] o2) {
        return o2[0] - o1[0];
    }
});

This would also run much faster as you don't need to manually swap the element in all dependent rows.

So if you can re-structure the rest of your code to accommodate the sorting without other major performance implications, I would do so.

Otherwise, you'll probably have to implement a manual sorting like suggested in the other answers, or you can transpose the array before and after the sort, although I doubt that would be faster.

Answer 5

IMHO, the good method is to sort only the indexes, but with a custom comparator that compares the values. It is just a slight variation from this solution proposed by 0Andrea. The difference is that here we have two different arrays, one for the indexes, one for the values instead of having multicolumns rows.

The interest of doing so is that you do not have to implement a sort algorythm and simply use TimSort natively implemented in the JDK. Here is a Junit implementation

public class SortTest {
    Integer points[][] = {
        { 12, 13, 10, 0, 0, 0 },
        { 1, 2, 3, 4, 5, 6 }, 
    };

    private Integer[] sort(Integer tab[][]) {
        IndexComparator<Integer> comparator = new IndexComparator<>(tab[0]);
        List<Integer> indexList = (List<Integer>) new ArrayList<>(Arrays.asList(tab[1]));
        Collections.sort(indexList, comparator);
        Integer[] result = new Integer[indexList.size()];
        return indexList.toArray(result);
    }

    private static class IndexComparator<T extends Comparable> implements Comparator<Integer> {
        Integer[] values;

        public IndexComparator(Integer[] values) {
            this.values = values;
        }

        @Override
        public int compare(Integer t, Integer t1) {
            return values[t1-1] - values[t-1];
        }
    }

    @Test
    public void test() {
        Integer[] result = sort(points);
        assertEquals(new Integer[]{2,1,3,4, 5, 6}, result);
        Integer[] values = new Integer[result.length];
        for (int i=0; i<values.length; i++) {
            values[i] = points[0][result[i] - 1];
        }
        assertEquals(new Integer[]{13,12,10,0,0,0}, values);
    }
}