Insertion sort (Haskell)

From LiteratePrograms

Other implementations: ACL2 | C | C, simple | Eiffel | Erlang | Forth | Haskell | Io | Java | Lisp | OCaml | Python | Python, arrays | Ruby | Scala, list | Smalltalk | Standard ML | Visual Basic .NET

This is a simple example of the insertion sort sorting algorithm, written in Haskell. This implementation will sort an arbitrary length list, using a user-defined sorting predicate (such as <= for a standard numerical sort).

Implementation

Insertion sort takes a predicate that compares two values of the same type. It returns a function that takes a list of that comparable type and returns a sorted version of the list.

<<insertion_sort.hs>>=
insertion_sort :: (a -> a -> Bool) -> [a] -> [a]

The empty list can already be considered sorted.

<<insertion_sort.hs>>=
insertion_sort pred []     = []

In the case of non-empty lists, we recursively insert the first element of the list into an already insertion-sorted version of the rest of the list.

<<insertion_sort.hs>>=
insertion_sort pred (x:xs) = insert pred x (insertion_sort pred xs)

So, for example

insertion_sort (<=) [5,3,10] = insert (<=) 5 (insertion_sort (<=) [3,10])
                             = insert (<=) 5 (insert (<=) 3 (insertion_sort (<=) [10]))
                             = insert (<=) 5 (insert (<=) 3 (insert (<=) 10 (insertion_sort (<=) [])))

Which reduces to

                             = insert (<=) 5 (insert (<=) 3 (insert (<=) 10 []))

since

insertion_sort pred [] = []

To further evaluate the insertion sort function, we need to understand how the insert function works.

insert

The insert function takes a predicate that compares two values of the same type, an element of the comparable type, and a list of already sorted elements. It returns another sorted list, with the insertion element correctly positioned.

<<insertion_sort.hs>>=
insert :: (a -> a -> Bool) -> a -> [a] -> [a]

An element being inserted into an empty list requires no comparisons, and can simply be returned as a list.

<<insertion_sort.hs>>=
insert pred x [] = [x]

So, from our previous example we can determine that

insert (<=) 10 [] = [10]

and we are left with

insertion_sort (<=) [5,3,10] = insert (<=) 5 (insert (<=) 3 [10])

For non-empty lists, the element being inserted, x is compared to the first element of the list, y, using the predicate pred. If the predicate evaluates to True then x is assumed to be lower in the ordering than y, and is prepended to the sorted list. Otherwise, if the predicate evaluates to false, then y is considered lower in the ordering than x, and must remain the first element in the list. The element x must then be inserted somewhere after y in the list.

<<insertion_sort.hs>>=
insert pred x (y:ys)
  | pred x y = (x:y:ys)
  | otherwise = y:(insert pred x ys)

Continuing with our example, we can see that 3 <= 10, so

insert (<=) 3 [10] = 3:10:[]
                   = [3,10]

However, 5 is not <= 3, so

insert (<=) 5 [3,10] = 3:(insert (<=) 5 [10])
                     = 3:(5:10:[])
                     = [3,5,10]

As a result

insertion_sort (<=) [5,3,10] = [3,5,10]

and the list is sorted.

Testing

The insertion sort implementation can easily be tested in an interactive Haskell environment such as Hugs or the Glasgow Haskell Compiler's GHCi. For example, after loading insertion_sort.hs into GHCi, typing

insertion_sort (<=) [1, 5, 6, 4, 3]

at the prompt produces the sorted list

[1,3,4,5,6]

Since the insertion sort implementation is generic, we can also sort non-numeric lists:

*Main> insertion_sort (<=) ["bob","alice","zoe","barry"]                
["alice","barry","bob","zoe"]

Download code