Insertion sort (Haskell)

From LiteratePrograms
Jump to: navigation, search
Other implementations: ACL2 | C | C, simple | Erlang | Forth | Haskell | Java | OCaml | Python, arrays | 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).

[edit] Implementation

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

insertion_sort :: (a -> a -> Bool) -> [a] -> [a]

The empty list can already be considered sorted.

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 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 []))


insertion_sort pred [] = []

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

[edit] 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.

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.

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.

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.

[edit] 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


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

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