CODEWITHSUNDEEP
javaarraysalgorithmsortingmapping
Akshat J.
Akshat J.

Reputation: 213

How to sort two arrays with one being sorted based on the sorting of the other?

So I have encountered this problem a lot of times. Let me explain. Say I have these two arrays: A1={1,2,3,4,5,6,7,8,9,10}; and A2={1,2,3,0,2,1,1,0,0,0};. What I require is this: When I sort A2, whatever swapping and shifting of elements takes place in A2, the same should take place in A1 as well. Basically I am trying to create a Map using two arrays instead of creating an actual HashMap or HashTable.

Finally the arrays should look like this: A1={4,8,9,10,1,6,7,2,5,3}; and A2={0,0,0,0,1,1,1,2,2,3};. The corresponding values of both arrays are still the same but the data is sorted based on A2. I need a way to do this kind of sort in the fastest way possible.

Any suggestions for this?

Upvotes: 7

Views: 6733

Answers (4)

Martin
Martin

Reputation: 141

If you can advocate the approach not being the parallel collection anti-pattern mentioned above (you can easily for big data), the fastutils offer a solution in the class it.unimi.dsi.fastutil.Arrays. There are several sorting methods with an explicit comparator and swapper. Let say you want to sort UUIDs (stored as two longs each) but keep the track of their original indexes. Here you go:

long[] uuids = ..
int[] indexes = new int[uuids.length / 2];
// fill indexes
java.util.Arrays.parallelSetAll(indexes, i -> i);

IntComparator comparator = (k1, k2) -> {
        int cmp = Long.compare(uuids[2 * indexes[k1]], uuids[2 * indexes[k2]]);
        if (cmp == 0) {
            cmp = Long.compare(uuids[2 * indexes[k1] + 1], uuids[2 * indexes[k2] + 1]);
        }
        return cmp;
    };

Swapper swapper = (k1, k2) -> {
        int tmp = indexes[k1];
        indexes[k1] = indexes[k2];
        indexes[k2] = tmp;
    };

it.unimi.dsi.fastutil.Arrays.parallelQuickSort(0, indexes.length, comparator, swapper);

Upvotes: 0

Taylor
Taylor

Reputation: 26

You could try creating an object based on the data that you actually have. In this case the object might contain two fields, numbers and occurrences. Then implement a comparator to compare by the occurrences field.

Upvotes: 1

Unmitigated
Unmitigated

Reputation: 89204

You can create a two-dimensional array where each element is an array of length 2 and sort it based on the second element.

int[] A1 = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }, A2 = { 1, 2, 3, 0, 2, 1, 1, 0, 0, 0 };
final int[][] res = new int[A1.length][2];
for(int i = 0; i < res.length; i++) {
    res[i] = new int[] {A1[i], A2[i]};
}
Arrays.sort(res, (a,b)->Integer.compare(a[1], b[1]));
//Alternatively, Arrays.sort(res, Comparator.comparingInt(a -> a[1]));
for(final int[] a : res) {
    System.out.println(a[0] + " " + a[1]);
}

Upvotes: 2

Sankeeth Ganeswaran
Sankeeth Ganeswaran

Reputation: 477

Pair Class could do the trick here.

import java.util.*;
public class Main
{
    static class Pair implements Comparable<Pair>
    {
        int a1;
        int a2;
        Pair (int a1, int a2) //constructor 
        {
            this.a1 = a1;
            this.a2 = a2;
        }
        public int compareTo(Pair other) //making it only compare a2 values
        {
            return this.a2 - other.a2;
        }
    }
    public static void main(String[] args) 
    {
        int[] A1 = {1,2,3,4,5,6,7,8,9,10};
        int[] A2 = {1,2,3,0,2,1,1,0,0,0};
        Pair[] pairs = new Pair[A1.length];
        for (int i = 0; i < pairs.length; i++)
        {
            pairs[i] = new Pair(A1[i], A2[i]);
        }
        Arrays.sort(pairs);
        //printing values 
        for (int i = 0; i < A1.length; i++)
        {
            System.out.print(pairs[i].a1 + " ");
        }
        System.out.println();
        for (int i = 0; i < A2.length; i++)
        {
            System.out.print(pairs[i].a2 + " ");
        }
    }
}

By making a Pair class that holds 2 variables a1 and a2, you can override the compareTo method to only compare the a2 value, so that when Arrays.sort is called, the pairs in the Pair array will be swapped only according to the a2 values. You can then access the values in the pairs and print them out. This will produce your desired output.

Upvotes: 4

Related Questions