Mauro Bringolf

Currently geeking out as WordPress developer at WebKinder and student of computer science at ETH.

Generic sorting algorithms: A nice example of abstraction

August 30, 2017

One of the topics that keeps popping up in programming and computer science is the concept of abstraction. Especially programming languages offer many tools for abstraction of work, the most essential one being the function. A function allows a programmer to perform a task without having to deal with the implementation of this task. Given an implementation of a cosine function, knowing its signature is enough to use it. While this is not very astonishing, there are more elaborate tools and use cases for abstraction. And especially when learning a new programming concept, it might not be obvious why an abstraction is needed in the first place.

Sorting algorithms ask for abstraction

A sorting algorithm takes a list and computes its ordered version according to some global order among its elements. They usually work by repeatedly comparing pairs of elements and making decisions based on the outcome of the comparison. Algorithms like bubble sort, heap sort or merge sort all fall into this category. Very often these are described with integers as list elements to be sorted. This is very intuitive and perfect for understanding how such an algorithm works. Conceptually it is not hard to adjust the algorithm for a different class of things to be sorted. But to perform this adjustment on an implementation when needed seems redundant, because the algorithm does not really care what the elements of the list are. It only cares about their order. It would be nice if a given implementation of a sorting algorithm could be converted into a generic implementation that can work with all kinds of objects that need not be known in advance. Such a program could sort integers, strings, arrays or objects of any other class according to some order.

What abstraction is needed?

In order to implement a generic sorting algorithm that works with different classes of elements the necessary abstraction must be identified. If we take a sorting implementation for integers and hypothetically give it a list of objects of some class as input, what part of the code is going to break? All comparisons of list elements will probably fail, because operators like \( <, \leq, >, \geq \) usually do not work for objects but only for numbers. And that is exactly the part that needs to be abstracted: the comparison of two list elements. This should be the only part of a sorting algorithm that is specific to the type of elements being sorted. If it was possible to give the sorting algorithm a list of elements of plus detailed instruction on how to compare its elements it should be able to perform the task. This is the abstraction needed.

Leveraging programming constructs to do the abstraction

At first I wanted to write such a generic implementation, but quickly realized that there are multiple programming constructs that serve this purpose. So instead of providing a full implementation I decided to describe three possible solutions using different tools.

  1. First class functions: In programming languages like JavaScript functions are values. That means a function can be passed as a parameter to another function. A generic sorting algorithm in JavaScript could look something like the following:
    function sortingAlgorithm(input, comparator) {
      // Sort input array by comparing elements with the given comparator,
      // i.e. comparator( input[i], input[j] )
    }
    

    The comparator function can return different values (often -1,0 and 1) to indicate the outcome of the comparison. Then the comparing logic is external to the sorting algorithm and it is generic. A slightly different flavor of the same concept would be to use a higher order function. This function would take a comparator and return the sorting algorithm using this comparator, which then in turn could be called with different inputs that work with the comparator.

  2. Inheritance: Of course, classic object oriented programming has a mechanism for this abstraction and it is called inheritance. The sorting algorithm could work with a very generic interface that supports comparison logic. A given class can then implement this interface and be sorted with the generic algorithm. Here is a Java sketch:
    interface Comparable<T> {
      int compareTo( T other ) {
        // Return -1,0 or 1 depending on the relative order of this and other
      }
    }
    

    The generic sorting algorithm would then compare elements by calling their compareTo method which will execute the logic specific to a given class.

  3. Operator overloading:
  4. Some languages like C++ support operator overloading for classes. That means a class can specify how regular operators like +, - or < should operate on its objects. With operator overloading in place, objects of custom classes can be compared with the regular < operator that will use the comparison logic defined by the class. This way a sorting algorithm can be written with regular < comparisons for integers. All classes that give their own interpretation of comparisons via operator overloading can then be sorted with this implementation.

The main point of this post is to realize how different programming constructs and concepts are simply tools to achieve an abstraction. They are means to an end and most of them are pretty much equally strong and applicable, given a language that supports them. As shown, generic sorting algorithms are a very intuitive problem that can serve as motivating example when learning or teaching a certain abstraction tool in programming.