How to sort two or more arrays using single array?

Question

How can I sort three arrays by sorting an only a single array?

int arr[]={20,10,5,22};
int arr2[]={120,344,43,122};
int arr3[]={2234,12,23,3434};

what I want is to sort the first array arr and the remaining arrays must be sorted according to the index of the first array.

output:
  5 10 20 22

as in above arr before sorting index of 5 was 3 now it is 0. similarly index of 43 and 12 should be changed to 0

expected arrays after sorting would be would be

5 10 20 22

43 344 120 122

23 12 2234 3424

what I want as we swap element in bubble sort or any other swap we change to index of element by swapping. i want similar to other two arrays.

swap(arr[0],arr[2])

swap(arr1[0],arr1[2])

swap(arr2[0],arr2[2])

This is possible if I implement custom sorting but want something that will reduce code.

Duplicate of: [How to find the permutation of a sort in Java](https://stackoverflow.com/questions/11997326/how-to-find-the-permutation-of-a-sort-in-java) — Alex Shesterov, Nov 23 '21 at 14:40
What have you tried yourself? You learn programming by first thinking up an algorithm, and then implementing that. Coming here and asking people to do that for you ... means that you **slow** down your learning. And that link that you got gives you the first half: you need to understand the order of INDEXES in the first array, and then you apply that on the others. — GhostCat, Nov 23 '21 at 14:44
Of course it does answer your question: you find the permutation, then use this permutation to reorder all three arrays. Another way would be to use a custom "move array element" function, but there isn't anything built-in in Java: you would need to use a library or implement sort yourself. — Alex Shesterov, Nov 23 '21 at 14:45
@AlexShesterov I know the answer to the question by implementing the swapping algorithm but I was searching for easy one :) — disamaj964, Nov 23 '21 at 14:53

score 1 · Answer 1 · answered Nov 23 '21 at 15:21

Build list of indexes on the basis of the first arr array.
Sort each of the remaining arrays according to the indexes.

static int[] sort(List<Integer> indexes, int[] arr) {
    return indexes.stream().mapToInt(i -> arr[i]).toArray();
}

public static void main(String[] args) {
int arr[]={20,10,5,22};
    int arr2[]={120,344,43,122};
    int arr3[]={2234,12,23,3434};
    
    List<Integer> indexes = IntStream.range(0, arr.length)
                            .boxed()
                            .sorted(Comparator.comparingInt(i -> arr[i]))
                            .collect(Collectors.toList());
    System.out.println(indexes);
    
    Arrays.sort(arr);
    arr2 = sort(indexes, arr2);
    arr3 = sort(indexes, arr3);
    
    System.out.println(Arrays.toString(arr));
    System.out.println(Arrays.toString(arr2));
    System.out.println(Arrays.toString(arr3));
}

Output:

[2, 1, 0, 3]
[5, 10, 20, 22]
[43, 344, 120, 122]
[23, 12, 2234, 3434]

Oleg Cherednik · Accepted Answer · 2021-11-23T15:09:02.577

This is how you can do this. This is only an example and performance could be low.

Option 1. Lambda

public static void main(String... args) {
    int[] arr = { 20, 10, 5, 22 };
    int[] arr2 = { 120, 344, 43, 122 };
    int[] arr3 = { 2234, 12, 23, 3434 };

    sort(arr2, arr);
    sort(arr3, arr);
    Arrays.sort(arr);
}

private static void sort(int[] arr, int[] indices) {
    final class Pair {

        private final int index;
        private final int value;

        public Pair(int index, int value) {
            this.index = index;
            this.value = value;
        }

    }

    AtomicInteger pos = new AtomicInteger(0);

    IntStream.range(0, arr.length)
             .mapToObj(i -> new Pair(indices[i], arr[i]))
             .sorted(Comparator.comparingInt(one -> one.index))
             .map(pair -> pair.value)
             .forEach(value -> arr[pos.getAndIncrement()] = value);
}

Option 2. PriorityQueue

private static void sort(int[] arr, int[] indices) {
    final class Pair {

        private final int index;
        private final int value;

        public Pair(int index, int value) {
            this.index = index;
            this.value = value;
        }

    }

    Queue<Pair> queue = new PriorityQueue<>(Comparator.comparingInt(one -> one.index));

    for (int i = 0; i < arr.length; i++)
        queue.add(new Pair(indices[i], arr[i]));

    int i = 0;

    while (!queue.isEmpty())
        arr[i++] = queue.remove().value;
}

Option 3. TreeMap

private static void sort(int[] arr, int[] indices) {
    Map<Integer, List<Integer>> map = new TreeMap<>();

    for (int i = 0; i < arr.length; i++) {
        if (!map.containsKey(indices[i]))
            map.put(indices[i], new ArrayList<>());
        map.get(indices[i]).add(arr[i]);
    }

    int i = 0;

    for (List<Integer> values : map.values())
        for (int value : values)
            arr[i++] = value;
}

How to sort two or more arrays using single array?

2 Answers2