Sorting with Custom Comparator Functions

I don’t understand the last exercise in this course session : https://www.codecademy.com/paths/front-end-engineer-career-path/tracks/fecp-22-interview-skills/modules/wdcp-22-javascript-algorithm-practice/articles/sorting-with-custom-comparator-functions

When given an input array, we want to sort the array given to an explicit order.

const inputArray = ['a', 'b', 'c', 'd', 'e', 'f', 'n', 'y', 'g'];
const order = ['a', 'n', 'd', 'y'];

The comparator function explicitSort(inputArray, order) should return:

['a', 'n', 'd', 'y', 'b', 'c', 'e', 'f', 'g']

Here is the function:

const explicitSortWithComparator = (inputArray, order) => {

  

  const explicitComparator = (a, b) => {

    let indexA = order.length;

    let indexB = order.length;

    if (order.includes(a)) {

      indexA = order.indexOf(a);

    }

    if (order.includes(b)) {

      indexB = order.indexOf(b);

    }

    return indexA - indexB;

  }

  

  return inputArray.sort(explicitComparator).slice();

}

// Use this array to test your code:

const inputArray = ['a', 'b', 'c', 'd', 'e', 'f', 'n', 'y', 'g']

const order = ['a', 'n', 'd', 'y']

console.log(explicitSortWithComparator(inputArray, order));

module.exports = explicitSortWithComparator;

I don’t understand how this function works and how we can have the right result.

Thanks

Hi, can you specify what exactly you don’t understand?
The function explicitComparator is just the callback function of the inbuilt .sort() method. Maybe you are not aware how this works?

Hi,

Thank you for your answer.

In fact, what I don’t understand is how a and b are selected in the function explicitComparator. With inputArray and order given, here are rounds of calling explicitComparator:

  • Round 1:
    a=“b”
    b=“a”

  • Round 2:
    a=“c”
    b=“b”

  • Round 3:
    a=“d”
    b=“c”
    what we return is < 0 so we switch place between “c” and “d”

  • Round 4:
    a=“d”
    b=“b”
    I would have expected a=“e” and b=“c”, going forward in inputArray

Does my incomprehension makes sense ? :sweat_smile:

Yes, if you add some side effects to the callback function, just for testing, you’ll see how sort() bubbles through the array (just found out either):

const arr = [1,2,3,4,5]
const fn = (a,b) => {
 console.log(a, b)
 return 0
}
console.log(arr.sort(fn))

Output

So it’s takes pairs and moves on chronologically:
2nd, 1st,
4th, 3rd
until there is no full pair
then
3rd with all items before
and so on…

I copied paste your code, execute it in VS Code and I got a different result:

image

Weird…

Yes, indeed.
this article states that sort() by default uses the insertion sort algorithm:

  • JavaScript by default uses insertion sort for the sort() method. This means that it is not appropriate when sorting large data sets. When dealing with large data sets, one should consider other sorting algorithms such as merge sort.

Your output seems to show that: https://en.wikipedia.org/wiki/Insertion_sort
No idea why my output looks different.

Is it clear then how the explicitSortWithComparator callback works?

1 Like