Simplifying JS sorting once and for all: Sort(), localeCompare(), Sort keys in a Map, Sort Values in a Map

algorithm May 04, 2020

A very common function we all use in development is sorting. I use one of these at least once everyday. So I thought of putting some of these handy dandy sorting functionalities together.

sort():

This is the in-built javascript sort function. You can use this guy to do your basic sorts. In the background this uses Merge Sort so the run time of this is O(nlogn).

function sorting(arr) {
	return arr.sort();
}

console.log(sorting([4,3,2,1]))

// output: [1,2,3,4]

However this sort() comes with an optional compare function.

Say you want to sort a given array in descending order. How would that work? Lucky for us we can write a custom comparator within the sort.

function sorting(arr) {
	return arr.sort((a,b) => {
    	return b-a
    });
}

console.log(sorting([1,2,3,4]));

//output: [4,3,2,1]

localeCompare():

The localeCompare() is used to figure out if a reference string comes before or after as given string.

function sorting(str, referenceStr) {
	return str.localeCompare(referenceStr)
}
 sorting(a, b);
// output -1
sorting(b, a);
// output 1

In the case of ('a').localeCompare('b') I remember it by saying 'does b come before a? no? then return -1'

sort keys in Map:

Say you have a map and you need to sort it based on the keys of the map. There is several ways to do it. But here is my favorite way:

function sortKeys() {
    let map = new Map();
    map.set(1, "v");
    map.set(4, "v");
    map.set(2, "v");
    let sortedMap = new Map([...map.entries()].sort((a,b)=> b[0]-a[0]));
    return sortedMap;
}

console.log(sortedKeys());

// output: Map { 4 => 'v', 2 => 'v', 1 => 'v' }

sort values in Map:

Similar concept can be used for sorting the map based on values:

function sortValues() {
    let map = new Map();
    map.set("ORANGE", 1);
    map.set("APPLE", 4);
    map.set("KALE", 2);
    let sortedMap = new Map([...map.entries()].sort((a,b) => b[1]-a[1]));
    return sortedMap;
}
console.log(sortValues());

// output: Map { 'APPLE' => 4, 'KALE' => 2, 'ORANGE' => 1 }

Trying it all out with an exercise:

Let's do a Leetcode question where we can use all the stuff we just learnt.

Problem: Given a non-empty list of words, return the k most frequent elements.

Your answer should be sorted by frequency from highest to lowest. If two words have the same frequency, then the word with the lower alphabetical order comes first.

Input: ["i", "love", "leetcode", "i", "love", "coding"], k = 2
Output: ["i", "love"]
Explanation: "i" and "love" are the two most frequent words.
    Note that "i" comes before "love" due to a lower alphabetical order.

To do this problem, I simply use a HashMap. I iterate over the list and store the word as a key and the count as a value in my map.

Then I use the custom sort method to sort my map. Value needs to be sorted in descending order and key needs to be sorted alphabetically.

var topKFrequent = function(words, k) {
    let sortedWords = words;
    let map = new Map();
    let output = [];
    for(let i = 0; i < sortedWords.length; i++) {
        if(map.has(sortedWords[i])) {
            map.set(sortedWords[i], map.get(sortedWords[i])+1)
        } else {
            map.set(sortedWords[i], 1)
        }
    }
    let sortedMap = customSort(map)
    let keys = [...sortedMap.keys()];
    for(let i = 0; i < k; i++) {
        output.push(keys[i])
    }
    
    return output;
    
};

Simple enough. Now let's look at the customSort() function.


function customSort(map) {
    let sortedMap = new Map([...map.entries()].sort((a, b) => {
        if(a[1] < b[1]) {
            return 1;
        } else if (a[1] > b[1]) {
            return -1
        } else {
            return a[0].localeCompare(b[0]) // does b come after a? yes, returns 1 else returns 0;
        }
        
    }));
    
    return sortedMap;
}

Sorting is simple and there is so many ways to do it. I hope I helped you ton learn something new today! Happy Coding.