Sort a List based on the values in a map

Question

I am trying to sort a List of objects based on the values in the Map.

LinkedHashMap<String, Integer> map = new HashMap<>();
map.put("1233", 30);
map.put("1562", 5);
map.put("1243", 10);
map.put("1872", 20);

Based on values in this map I want to sort the following list:

l = [ 
     { id:1562,name:"xxx" },
     { id:1233,name:"yyy" },
     { id:1243,name:"zzz" },
     { id:1872,name:"xxx" }

    ]

Expected output:

l = [ 
     { id:1233,name:"yyy" },
     { id:1872,name:"xxx" },
     { id:1243,name:"zzz" },
     { id:1562,name:"xxx" }
    ]

I have tried bubble sort with specific condition but it is taking too much time:

 int n = l.size();
 for (int i = 0; i < n - 1; i++) {
    for (int j = 0; j < n - i - 1; j++) {
        if (map.get(l.get(j) > map.get(l.get(j+1)) {
            swap(j, l);
        }
    }
}

 private void swap(int j, List<L> l) {
        l temp = l.get(j);
        l.set(j, l.get(j + 1));
        l.set(j + 1, temp);
    }

Is there any better option, or any other data structure?

You should use a data structure that maintains sort like TreeMap (https://docs.oracle.com/javase/7/docs/api/java/util/TreeMap.html). HashMap does not guarantee sort order, even if you try to sort it. — pringi, Mar 08 '22 at 13:23
@pringi I guess OP wants to sort a list of entries, not a map. — Alexander Ivanchenko, Mar 08 '22 at 14:11
@pringi But you are right that dumping these entries to a `TreeMap` is a possible solution, although it differs a lot from the option of maintaining the list of `Map.Entry` objects. — Alexander Ivanchenko, Mar 08 '22 at 14:28
In Ruby (think pseudo-code): we are given `l` and `h = { "1233"=>30, "1562"=>5, "1243"=>10, "1872"=>20 }`. Compute the hash `g = h.values.each_with_index.sort_by { |v,i| -v }.to_h #=> {30=>0, 20=>3, 10=>2, 5=>1}`. Then `l.sort_by { |f| g[f[:id]] } #=> [{:id=>1562, :name=>"xxx"}, {:id=>1233, :name=>"yyy"}, {:id=>1243, :name=>"zzz"}, {:id=>1872, :name=>"xxx"}]`. — Cary Swoveland, Mar 08 '22 at 23:18

score 1 · Accepted Answer · answered Mar 08 '22 at 13:47

1

You could do it in one line using the method sort and a comparator, but not sure if it is effcient enough for your use case.

import java.util.Comparator;

.....

l.sort(Comparator.comparing(f -> map.get(f.getId()),Comparator.reverseOrder()));

answered Mar 08 '22 at 13:47

Eritrean

15,851
3
22
28

That will not compile, method `sort()` expects only one argument. – Alexander Ivanchenko Mar 08 '22 at 14:29
@AlexanderIvanchenko I think this is working, testing different cases. update you after testing. – Shafeeq Mohammed Mar 08 '22 at 14:42

Alexander Ivanchenko · Answer 2 · 2022-03-08T14:02:31.647

As I understand the problem, you want to sort a list of entries List<Map.Entry<Integer, String>> based on the values returned by my map Map<String, Integer> for each key in the descending order.

For that, you need to define a Comparator that will compare list elements based on entry keys:

Comparator<Map.Entry<Integer, String>> byKeyDesc =
            Comparator.<Map.Entry<Integer, String>>comparingInt(entry -> 
                    map.get(String.valueOf(entry.getKey()))).reversed();

And then and apply list.sort().

public static void main(String[] args) {
    Map<String, Integer> map =
            Map.of( "1233", 30, "1562", 5,
                    "1243", 10, "1872", 20);

    List<Map.Entry<Integer, String>> entryList = new ArrayList<>(
            List.of(Map.entry(1562, "xxx"),
                    Map.entry(1233, "yyy"),
                    Map.entry(1243, "zzz"),
                    Map.entry(1872, "xxx"))
    );

    Comparator<Map.Entry<Integer, String>> byKeyDesc =
            Comparator.<Map.Entry<Integer, String>>comparingInt(entry ->
                    map.get(String.valueOf(entry.getKey()))).reversed();

    entryList.sort(byKeyDesc);
    entryList.forEach(System.out::println);
}

Output

1233=yyy
1872=xxx
1243=zzz
1562=xxx

Sort a List based on the values in a map

2 Answers2