[Algorithm Tips & Tricks] Sorting with Custom Comparators (with a Leetcode Problem)

Introduction: Sorting

Sorting is one of the most important things in computer science, and is one of the first things taught.

​Given some data structure (typically an array), order the elements in a particular way.

A typical sort.

There's no one "best" sorting algorithm, and the algorithm chosen should be tailored for its particular use case.

However, all sorting algorithms follow the same procedure:

1. Compare two elements.
2. Decide what order they should be in.
3. Swap them (or reorder the container) so that the elements are in their correct positions.

​We'll focus on step (2) in this blogpost.

---

Custom Comparators

The "default" for sorting is either by ascending order for integers (1 -> 2 -> 3) or in alphanumeric order for strings ("a" -> "b" -> "c").

How do you sort in descending order for integers? Or reverse alphanumeric order for strings?

What if you weren't dealing with primitive variables like integers or strings, but had a container of objects and needed to be sorted on multiple keys? For example, if you had a Person class with fields for name and age, and wanted to sort by name, then age.
[ { name: "Alex", age: 30 }, { name: "Bill", age: 25 }, { name: "Bill", age: 40 } ]

You can handle custom sorting by using custom comparators.​

A custom comparator is a function that takes two instances of whatever data type you're trying to sort, and the function has logic that returns true if the second argument needs to be to the left of the first argument. Basically, if the thing on the left (first argument) needs to be swapped with the (second argument).

---

Custom Comparators with Standard Libraries

Most languages come with a "sort" function in their standard library. For example, in C++ you can sort an array ("vector", in C++) like so:

However, what if we wanted to sort in reverse order? We could create a custom comparator that says "larger elements should go to the left" and pass that into the sort function.

As you can see, it's very easy to write a simple function that controls how the standard library's "sort" function determines how to order the array. We can make our comparator as complex as we need too.

---

[Example] Sort Integers By The Number Of 1-Bits (Leetcode)

This Leetcode problem is a great example of custom sorting. It asks you to sort an array of integers by the number of 1-bits each number has in its bit-representation.

We can use the standard library's sort function for this problem, and just create our own custom comparator to handle the comparison part.

Note: The code above was written for readability. There are special tricks for finding the number of bits in an integer that would make the code faster.

​Like this content and want more? Feel free to look around and find another blog post that interests you. You can also contact me through one of the various social media channels. 

Twitter: @srcmake
Discord: srcmake#3644
Youtube: srcmake
Twitch: www.twitch.tv/srcmake
​Github: srcmake