November 14th, 2017

Sorting Lists with Comparison Functions


Java 8







In this discovery I look at sorting lists in different programming languages for non-trivial objects. The languages I use are my core languages: Java, JavaScript, Swift, Python, PHP, and C. I've used all these languages in larger projects and wish to stay proficient in them. Throughout this article I show snippets of code in each language, but you can also check out the full code on GitHub. Let's get started!

List<Person> list = Arrays.asList(new Person("Andrew", "Jar."), new Person("Thomas", "Cau."), new Person("Joe", "Smi."), new Person("Ben", "Fis.")); list = .sorted(Comparator.comparing(Person::getLast)) .collect(toList());

You may have expected the Java code to be messy and verbose with iterators and complex comparison functions. With Java 8 it is short and concise thanks to streams and the comparator API. Also using the short-hand lambda syntax (method reference) I was able to write Person::getLast instead of (p) -> p.getLast(). Most of the code in the full example is for creating the Person POJO.

let people = [ {first: "Andrew", last: "Jar."}, {first: "Thomas", last: "Cau."}, {first: "Joe", last: "Smi."}, {first: "Ben", last: "Fis."} ];; people.sort(function(a, b) { return a.last > b.last ? 1 : 0; });;

The JavaScript version is even simpler. I just passed a call back function to sort() and it uses the callback when making comparisons.

One thing that was strange when executing this code is that both invocations produced the sorted array even though the first occurs before people is sorted. This is because console functions are asynchronous in some environments. Therefore we may not get the results at the time we expect. You can't always trust console!

struct Person { let first: String let last: String } var list = [ Person(first: "Andrew", last: "Jar."), Person(first: "Thomas", last: "Cau."), Person(first: "Joe", last: "Smi."), Person(first: "Ben", last: "Fis.") ] list.sort { $0.last < $1.last }

I really like the Swift implementation for sorting. In general I prefer using classes over structs in Swift (just a personal preference!), but in a simple case like this one a struct makes perfect sense.

If you don't know much Swift the sorting operation may look a bit confusing. The sort() method on the Array type is passed a Swift closure (not to be confused with a closure in JavaScript), which is basically a callback function. Since the Swift compiler knows that the sort() function takes a closure you can use parameter shorthands which are represented as $1 and $2 ($1 being the first parameter, $2 being the second, etc.)1. I also utilized trailing closure syntax which can be used when the closure is the last parameter of a function. Trailing closure syntax enables the removal of a function invocations parenthesis, and you can see sort() uses no parenthesis2! All these tricks are fun to look into and allow for very concise Swift code.

$array = array(new Person('Andrew', 'Jar.'), new Person("Thomas", "Cau."), new Person("Joe", "Smi."), new Person("Ben", "Fis.")); function comparator($a, $b) { return $a->last < $b->last ? -1 : 1; } uasort($array, 'comparator');

The PHP solution may be my least favorite. I created the People object and an array of People. uasort() is used for user defined comparisons where argument one is the array and argument two is the string name of the comparison function. Why can't I treat the comparison function as a first class citizen and pass it as the second uasort() argument? This code feels ugly.

people = [{"first":"Andrew", "last":"Jar."}, {"first":"Thomas", "last":"Cau."}, {"first":"Joe", "last":"Smi."}, {"first":"Ben", "last":"Fis."}] def last(item): return item["last"] # reverse optional argument can be removed people.sort(key=last, reverse=False)

As you probably guessed, the winner for most concise comparison sort goes to Python. Thanks to optional arguments, the sort() function is really sleek!

typedef struct { char first[20]; char last[20]; } person; int main() { person andrew; strcpy(andrew.first, "Andrew"); strcpy(andrew.last, "Jar."); person thomas; strcpy(thomas.first, "Thomas"); strcpy(thomas.last, "Cau."); person joe; strcpy(joe.first, "Joe"); strcpy(joe.last, "Smi."); person ben; strcpy(ben.first, "Ben"); strcpy(ben.last, "Fis."); person people[] = {andrew, thomas, joe, ben}; // Get the length of the people array int size = sizeof(people) / sizeof(people[0]); for (int i = 0; i < size; i++) { printf("%d - %s %s \n", i + 1, people[i].first, people[i].last); } printf("\n"); qsort(people, size, sizeof(people[0]), compare); for (int i = 0; i < size; i++) { printf("%d - %s %s \n", i + 1, people[i].first, people[i].last); } } static int compare(const void *a, const void *b) { person *pA = (person *) a; person *pB = (person *) b; return strcmp(pA->last, pB->last); }

As you also likely guessed, the C code is by far the most involved. The structs do make the sorting easier (I originally tried sorting lists of lists of lists, but the pointers got out of control and I couldn't figure it out!). I utilized the standard libraries qsort() function and passed in a comparison function3.

[1] Matthew Mathias & John Gallagher, Swift Programming: The Big Nerd Ranch Guide (Atlanta, GA: Big Nerd Ranch, 2016), 130

[2] Ibid., 131

[3] "C Program to Sort an array of names or strings",