How to sort an array with respect to another array if there are duplicates?

Question

I could sort an array with respect to another if there is unique value. But since i am trying sort the below given array:

initial fuel[]={1,9,9,2,9,9};
initial cost[]={2,6,5,4,3,1};

I wanted to sort fuel array then again wanted to sort cost array with respect to fuel array.
I wanted output like given below:

final fuel[]={1,2,9,9,9,9};
final cost[]={2,4,6,5,3,1};

Below is my code:

public static void sort(List<Integer> c, List<Integer> f) {
    List<Integer> cc = new ArrayList<>(c);
    Collections.sort(c);

    List<Integer> al = new ArrayList<>();

    int i = 0;
    while (i < c.size()) {
        int temp = c.get(i);
        int index = cc.indexOf(temp);
        al.add(f.get(index));

        cc.remove(index);
        f.remove(index);

        i++;
    }

    for (int value : c)
        System.out.print(value + " ");
    System.out.println();
    for (int value : al)
        System.out.print(value + " ");
}

How can I use comparator to sort in this ways? Also how to use stream api for the same?

WJS · Accepted Answer · 2020-11-29T18:45:55.300

If you always want to associate a given fuel value with cost then I suggest you create a class to hold them. This will allow proper sorting while keeping both values together.

int[] fuel = { 1, 9, 9, 2, 9, 9 };
int[] cost = { 2, 6, 5, 4, 3, 1 };

This creates the class and sorts it based on the fuel value, and puts it in a list.

List<FuelInfo> fuelInfo =
        // generate array indices
        IntStream.range(0, fuel.length)
        
        // create the objects 
        .mapToObj(i -> new FuelInfo(fuel[i], cost[i]))

        // sort them based on fuel value 
        .sorted(Comparator.comparing(FuelInfo::getFuel))

        // put them in a list.
        .collect(Collectors.toList());

 
fuelInfo.forEach(System.out::println)

Prints

[1, 2]
[2, 4]
[9, 6]
[9, 5]
[9, 3]
[9, 1]

You can copy the individual values back to a list as followis:

List<Integer> fuelList = fuelInfo.stream()
        .map(FuelInfo::getFuel).collect(Collectors.toList());
List<Integer> costList = fuelInfo.stream()
        .map(FuelInfo::getCost).collect(Collectors.toList());

If you want to maintain the default order for duplicates then this will work since the sorting in Java is stable (insertion order is maintained when comparing equals values). This works by using sorting the indices based on the value of the fuel array and then using the sorted indices to build the cost list in properly sorted order.

Comparator<Integer> comp = (a,b)->Integer.compare(fuel[a],fuel[b]);

Comparator<Integer> comp =
        (a, b) -> Integer.compare(fuel[a], fuel[b]);

List<Integer> sortedFuel = Arrays.stream(fuel).sorted()
        .boxed().collect(Collectors.toList());

List<Integer> sortedCost = IntStream.range(0, fuel.length)
        .boxed().sorted(comp).map(a -> cost[a])
        .collect(Collectors.toList());

System.out.println(sortedFuel);
System.out.println(sortedCost);

Prints

[1, 2, 9, 9, 9, 9]
[2, 4, 6, 5, 3, 1]

The FuelInfo class


class FuelInfo{
    private int fuelAmt;
    private int cost;
    public FuelInfo(int fuel, int cost) {
        this.fuelAmt = fuel;
        this.cost = cost;
    }
    public int getFuel() {
        return fuelAmt;
    }
    public int getCost() {
        return cost;
    }
    public String toString() {
        return String.format("[%s, %s]", fuelAmt, cost);
    }
}

Thank you. Is there a way to do the same without creating a new class. I wanted to keep both array in separate arrayList. Hope you got my question. — Khushtar Hussain, Nov 29 '20 at 17:44
Not if you want to maintain a strict association of both fuel value and costs after sorting. But see my amended solution on easily copy them back. to individual lists. — WJS, Nov 29 '20 at 18:15
@KhushtarHussain I put my answer with what you wanted (hopefully) — null_awe, Nov 29 '20 at 18:28

score 0 · Answer 2 · answered Nov 29 '20 at 18:23

Use the following:

Integer[] fuel = { 1, 9, 9, 2, 9, 9 };
Integer[] cost = { 2, 6, 5, 4, 3, 1 };
// Map each fuel number to a list of costs, keeps in order
// meaning that 9 will point to [6, 5, 3, 1] which is what
// we want.
Map<Integer, List<Integer>> map = new HashMap<>();
for (int i = 0; i < fuel.length; i++) {
    if (!map.containsKey(fuel[i])) map.put(fuel[i], new ArrayList<>());
    map.get(fuel[i]).add(cost[i]);
}
List<Integer> sortedFuel = Arrays.asList(fuel);
Collections.sort(sortedFuel);
List<Integer> rearrangedCost = new ArrayList<>();
for (int val : sortedFuel) {
    // Get the first value of the mapping, which is the first that
    // appears in cost
    rearrangedCost.add(map.get(val).get(0));
    map.get(val).remove(0);
}
System.out.println("final fuel = " + sortedFuel);
System.out.println("final fuel = " + rearrangedCost);

Output:

final fuel = [1, 2, 9, 9, 9, 9]
final fuel = [2, 4, 6, 5, 3, 1]

Hope this is what you are looking for!

score 0 · Answer 3 · 2020-12-27T13:31:29.490

Assuming that the lengths of these two arrays are the same, you can create a list of map entries containing pairs of elements from these arrays, and sort this list first by key and then by value, or you can sort it only by key and the values are sorted in insertion order:

Integer[] fuel = {1, 9, 9, 2, 9, 9, 2};
Integer[] cost = {2, 6, 5, 4, 3, 1, 5};

List<Map.Entry<Integer, Integer>> entryList = IntStream.range(0, fuel.length)
        // create a Map with one entry 'fuel-cost'
        .mapToObj(i -> Map.of(fuel[i], cost[i]))
        // flatten all entries into one stream
        .flatMap(map -> map.entrySet().stream())
        // sorting entries
        .sorted(Comparator
                // first by key - fuel - in ascending order
                .comparing((Map.Entry<Integer, Integer> entry) -> entry.getKey())
                // then by value - cost - in descending order, or without a
                // second comparator, duplicates are sorted in insertion order
                .thenComparing(Map.Entry::getValue, Comparator.reverseOrder()))
        // return sorted list of entries
        .collect(Collectors.toList());

System.out.println(entryList); // [1=2, 2=5, 2=4, 9=6, 9=5, 9=3, 9=1]

// if you want to replace the contents of the arrays
IntStream.range(0, entryList.size()).forEach(i -> {
    fuel[i] = entryList.get(i).getKey();
    cost[i] = entryList.get(i).getValue();
});

System.out.println(Arrays.toString(fuel)); // [1, 2, 2, 9, 9, 9, 9]
System.out.println(Arrays.toString(cost)); // [2, 5, 4, 6, 5, 3, 1]

^{See also: Collect a list of ids based on multiple fields}

How to sort an array with respect to another array if there are duplicates?

3 Answers3

Linked