Insertion sort (Erlang)

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 Erlang. This implementation will sort an arbitrary length list.

Main algorithm

When sorting a list with insertion sort, we keep track of two things:

• The list of elements we have yet to insert;
• The list of elements already inserted, which is always in sorted order.

The insertion sort begins with an unsorted list of elements to insert, List, and an empty list of already inserted elements.

<<sort>>=
sort(List) when is_list(List) ->
    sort(List, []).

Sorting proceeds by recursively inserting the head of the unsorted list into the appropriate location in the sorted list. Sorting is complete when the unsorted list is empty.

<<sort>>=
sort([H | T], Acc) ->
    sort(T, insert(H, Acc, []));
sort([], Acc) ->
    Acc.

Several auxiliary definitions allow the insertion of a single element into the appropriate location within a sorted list. To make the sort stable, we need to pass equal items to the head of the accumulator (thus slack inequality). We'll use another accumulator here to avoid non-tail recursion.

<<insert>>=
insert(Elem, [H | T], Acc) when Elem >= H ->
    insert(Elem, T, [H | Acc]);
insert(Elem, List, Acc) ->
    lists:reverse(Acc) ++ [Elem | List].

We package the insertion sorting algorithm within an appropriately named module.

<<isort.erl>>=
% Sort a list %
-module(isort).
-export([sort/1]).
sort
insert

Alternative implementation

The idea of this implementation came to me when I tried to implement gnome sort in Erlang.

The previous code may be somewhat beautified, if you combine sort/2 and insert/2 in the only function. The resulting function sort/3 operates two accumulators at once, one for storing the sorted part of the list and another for storing elements of the sorted part of the list, that are greater than an element being examined.

<<isort2.erl>>=
-module(isort2).
-export([sort/1]).
sort(List) when is_list(List) ->
    sort(List, [], []).
sort([], Acc, _) ->
    lists:reverse(Acc);
sort(List = [X | _], [Y | AccT], Temp) when X < Y ->
    sort(List, AccT, [Y | Temp]);
sort([X | T], Acc, Temp) ->
    sort(T, lists:reverse(Temp) ++ [X | Acc], []).

Download code