1

I am trying to create a TreeMap that sorts a created map by value. My code right now is:

public static TreeMap<String, Integer> sortedMap(Map<String, Integer> map)
{
    TreeMap<String, Integer> freq = new TreeMap<>(new Comparator<String>() {
        @Override
        public int compare(String s1, String s2)
        {
            return map.get(s1) >= map.get(s2) ? -1 : 1;
        }
    });

    freq.putAll(map);

    return freq;
}

However, from my understanding, this would have a time complexity of around O(n2), and wanted to see if I could use something like merge sort or just a factor way to sort the map.

amenkes319
  • 21
  • 4
  • 4
    This doesn't work. The `TreeMap` would use this comparator to work out where to insert a key into the tree; but unless it's already in the map, it would give an NPE, and if it is already in the map, it would use the old value. – Andy Turner Apr 21 '21 at 22:15
  • @AndyTurner: note that OP calls `get` not on the `TreeMap`, but on the input map. So it will work as long as the result is treated as immutable (or more precisely: as long as only keys present in the input are ever put into the `TreeMap`). – Joachim Sauer Apr 21 '21 at 22:17
  • @JoachimSauer in this construction method, that's OK; afterwards, it's very brittle e.g. if you were to modify the new map with a key not present in the original. But also, it doesn't work because the comparator isn't implemented correctly :) – Andy Turner Apr 21 '21 at 22:18
  • 1
    https://stackoverflow.com/q/109383/869736 has many answers to this question. – Louis Wasserman Apr 21 '21 at 22:21
  • Where does `O(n^2)` come from? – Boris the Spider Apr 21 '21 at 22:25
  • @BoristheSpider tbh, it just appeared to look similar to insertion sort, but I don't really have any basis on that, it very well might not be – amenkes319 Apr 21 '21 at 23:29
  • This code is not even a sort, let alone an insertion sort. It's just a comparator. – user207421 Apr 21 '21 at 23:35
  • @user207421 yes ik, thats why i said appeared to look similar. because of how the comparisons are made, similar to comparisons you would make when using insertion sort – amenkes319 Apr 21 '21 at 23:37
  • Similar to comparisons you would make in *any* sort, or any search, or insert, or anywhere else that `Comparators` are used. This is a tree insert. – user207421 Apr 22 '21 at 00:38

0 Answers0