One of the most basic computational tasks is, when given a list of items, arrange them in some sort of ordering (least to greatest, or vice versa), though this has admittedly fallen out of popularity in recent years.
ME: please show me the posts in the order that they were made
— wint (@dril) August 4, 2016
COMPUTER: thats too hard. heres some tweets i think are good. Do you like this
This problem is called sorting. Sorting is the starting point for solving many problems: scheduling, ranges, computational geometry, pathfinding, and so on. As you can guess, there are lots of kinds of items we might wish to sort, but all of the basic ideas can be communicated by considering lists of integers, so that's what we'll do for now. The standard version of the problem is stated as follows:
Given a list $a_1, a_2, \dots, a_n$ of integers, produce a list that contains $a_1, a_2, \dots, a_n$ in ascending order.
This seems daunting at first because it is quite unlike anything we've seen before: we are essentially asked to rearrange elements of a list. But as you may expect, because this is a problem about lists, we can expect that the solution of this problem will be recursive, so it makes sense to approach it recursively.
(cons head tail) as usual and we have two pieces of information: head and the result of the recursive call (sort tail) (assuming that our function is called sort).
In other words, we have a member of our original list, head, and the rest of the list, tail, already sorted. This greatly simplifies our problem: all we have to do is find the right spot for head.
This is not unlike the problem of pulling out a book at the library and trying to find the place where it came from to put it back later on (even though you should not do this). Since the shelves are sorted, this makes finding the right spot for our book much less work than if all the books were out of order.
In other words, we need to insert our element $n$ into right spot in the list. Again, we can think about how to do this. Since our list is already sorted, we can go through our list one item at a time:
Note that these are the only two possibilities because by traversing the list recursively, we are only ever comparing $n$ with the first element of a sorted list. This gives us the following function definition.
(: insert (-> Integer (Listof Integer) (Listof Integer)))
;; Insert given integer into given sorted list
(define (insert n ns)
(match ns
['() (cons n '())]
[(cons head tail)
(if (< n head)
(cons n ns)
(cons head (insert n tail)))]))
It is very important to note that insert only works if the list that's provided is sorted. We can then use this in our main sorting algorithm, the insertion sort.
(: insertion-sort (-> (Listof Integer) (Listof Integer)))
;; Given list of integers, produce sorted list of same integers
(define (insertion-sort ns)
(match ns
['() '()]
[(cons head tail) (insert head (insertion-sort tail))]))
There are a few interesting things to note here. The first is the structure of the function. Does it look familiar? It appears to have the same structure as a fold! Indeed, insert is a function of type (-> A B B), where A is Integer and B is (Listof Integer). Then one may wonder if it's possible to express this as a fold and we get the following:
(: insertion-sort (-> (Listof Integer) (Listof Integer)))
;; Given list of integers, produce sorted list of same integers
(define (insertion-sort ns)
(foldr insert '() ns))
Now, we have a fine sorting algorithm but it happens to work only for lists of integers and only in one direction. It's not hard to see how we might change our algorithm to work with other comparison functions: just swap the function in insert. Just as with filter we can generalize our sorting function by turning it into a higher-order function and accepting a comparison function as input (something of type (-> A A Boolean)). This happens to take care of another issue: how to make the function polymorphic.
It seems like we have successfully solved our problem. However, there are more questions we can ask. For instance, let's consider the action of the insertion sort algorithm. At first glance, it appears that all we're doing is going down our list and inserting each element in the right place. Not bad. But there is some work that's hidden that isn't obvious.
For example, suppose we try to sort a list with $n$ elements that is sorted but in exactly the wrong order. What we see in our recursive step is an insertion of an element into a sorted list, which takes $n-1$ comparisons and goes at the end of the list. But we still haven’t accounted for the work to sort those $n-1$ elements. We get the same problem: we might have had to search $n-2$ elements for the right place to put our element.
If we keep going down this road, we discover that we have to make up to $1 + 2 + \cdots + (n-1) = \frac{n \cdot (n-1)}2$ comparisons between two elements. This happens to be the number that you get when you compare every element in the list with every other single element in the list: from a set of $n$ elements, the number of ways to choose two of them is $\binom n 2 = \frac{n \cdot (n-1)} 2$.
In other words, there are some inputs where we will be doing the maximum amount of work possible. A natural question to ask is: Can we do better? Is there a way to avoid this?