The JS Sort() Function

javascript, sort, leetcode2724

Main project image

Given an array arr, a function fn, return a sorted array sortedArr. fn only returns numbers and those numbers determined the sort order of sortedArr. sortedArr must be sorted in ascending order. Assume that fn will never duplicate numbers for given array.

To solve this, consider the example 1. We cannot simply use sort() without any parameters because the array contains objects. Fortunately,sort() takes a optional compareFn function which determines the order of the elements.

compareFn takes the following arguments. a for the first element and b for the second. It should return one of the following:

To memorize this, (a,b) => a - b would sort numbers in ascending order.

Input: arr = [{"x": 1}, {"x": 0}, {"x": -1}], fn = (d) => d.x
Output: [{"x": -1}, {"x": 0}, {"x": 1}]
Explanation: fn returns the value for the "x" key. So the array is sorted based on that value.

So, we map the lements into a new array mapped with their value, index and element.

Then we invoke sort(...) where we sort the value returned by fn. We return either -1 or 1 depending on the value of a and b, otherwise we compare the original indices.

We return the final array with the original elements sorted.

var sortBy = function(arr, fn) { 
    // map the elements with their transformed values and original indicies
    const mapped = arr.map((element, index) => {
        return {
            value: fn(element),
            index: index,
            element: element
        }
    })


    mapped.sort((a, b) => {
        if (a.value !== b.value) {
            // compare the transformed values
            return a.value < b.value ? -1 : 1
        } else {
            // if values are equal, compare original indices
            return a.index - b.index
        }
    })

    return mapped.map(item => item.element);
};

mapped.sort(...) can also be further simplified on complexity:

mapped.sort((a, b) => {
        if (a.value !== b.value) {
            return a.value - b.value;
        } 
    })