Sorting three arrays using third array as pivot

Question

I have 3 arrays

a[n] , b[n] ,c[n]

a and b arrays are entered by the user and c is calculated as

c[i] = b[i] - a[i] + 1

Sorting the c array is easy. I sorted it by

Arrays.sort(c) method

Now I have to sort arrays a & b according to c as follows

For Example -

a[5] ={1 , 3 , 5 , 7 , 9 }

b[5] ={5 , 4 , 7 , 8 , 10 }

Then c[] will be calculated as

c[i] = b[i] - a[i] +1.

c[5] ={5 , 2 , 3 , 2 , 2}

Now sorting the c array results in

c[5] = { 2 , 2 , 2 , 3 , 5 }

Now I also want a[i] and b[i] as

a[5]={ 3 , 7 , 9 , 5 , 1 }

b[5]={ 4 , 8 , 10 , 7 , 5 }

such that the now the relationship between arrays will be maintained for each element 'i'

c[i] = b[i] - a[i] + 1

Answer 1

Using array will be way too messy. You can keep them in a class:

public class Triplets {
    public int a;
    public int b;
    public int c;
}

Then we can take input in this class instead of seperate arrays (for example) :

int [] a ={1 , 3 , 5 , 7 , 9 };
int [] b ={5 , 4 , 7 , 8 , 10 };


Triplets [] tripletses = new Triplets[5];

for (int i = 0 ; i < tripletses.length ; i++){
    tripletses[i] = new Triplets();
    tripletses[i].a = a[i];
    tripletses[i].b = b[i];
    tripletses[i].c = tripletses[i].b - tripletses[i].a + 1;
}

Of course you need to use your own input logic there. Now we can sort this array using a Custom Comparator

Arrays.sort(tripletses, new TripletsComp());

And of course the Comparator:

 public class TripletsComp implements Comparator<Triplets> {
        @Override public int compare(Triplets e1, Triplets e2) {
            if(e1.c > e2.c){
                return 1;
            }else if (e1.c == e2.c){
                return 0;
            }
            else { return -1; }
        }
    }

If you are not familiar with Comarator, have a read about them :)

Answer 2

There are two solutions to this problem:

1. Make a class AbcHolder that holds three elements corresponding to a[i], b[i], and c[i], sort it on the c field using a custom sorter, and write out as, bs, and cs back to their corresponding arrays, or
2. Make an array of indexes idx[], populate it with numbers from zero to c.length-1, inclusive, and sort it instead of sorting c[]. Use custom comparer to compare cs at the corresponding indexes. After that you can reorder b and a on the matching indexes.

Answer 3

When you sort c[5]. You can sort it by value and you will get an array of corresponding key value pair.

It will return an array like this

array(5) { [1]=> int(2) [3]=> int(2) [4]=> int(2) [2]=> int(3) [0]=> int(5) } 

By using the keys of above sorted c[5] array you can get the corresponding values of a[5] and b[5];

I hope this s helpful to you.

Answer 4

If you are sorting them without using any predefined function then you can go for any of the stable sorts such as insertion, merge or bubble sort and swap the numbers in the first array whenever you are performing a swap in the second.

Answer 5

Best way I found, without creating new arrays is using a Swapper. Allowing you to perform other operations when the sort swaps between two indexes. I used it.unimi.dsi.fastutil.Arrays.quickSort(int, int, IntComparator, Swapper), from FastUtil. This is my code:

public static void main(String[] args) {
    final int SIZE = 25;
    Random rand = new Random();
    int[] a = new int[SIZE];
    int[] b = new int[SIZE];
    int[] c = new int[SIZE];

    for (int i = 0; i < a.length; i++)
        a[i] = rand.nextInt(100);
    for (int i = 0; i < b.length; i++)
        b[i] = rand.nextInt(100);
    for (int i = 0; i < c.length; i++)
        c[i] = b[i] - a[i] + 1;

    Arrays.quickSort(0, SIZE, new AbstractIntComparator() {

        @Override
        public int compare(int k1, int k2) {
            return Integer.compare(c[k1], c[k2]);
        }
    }, new Swapper() {

        @Override
        public void swap(int i, int j) {
            // Swap in c
            int temp = c[i];
            c[i] = c[j];
            c[j] = temp;

            // Swap in a and b
            temp = a[i];
            a[i] = a[j];
            a[j] = temp;
            temp = b[i];
            b[i] = b[j];
            b[j] = temp;
        }
    });
}