Insertion sort (Erlang)

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

[edit] 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. Since the list of inserted elements is empty, the first sorting operation simply moves the head of the unsorted list into the sorted list.

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

sort([H | T], []) ->
    sort(T, [H]);

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.

<<insertion_sort>>=
sort([H | T], [AccH | AccT]) when H =< AccH ->
    sort(T, [H, AccH | AccT]);

sort([H | T], [AccH | AccT]) ->
    NewAcc = [AccH | sort(H, AccT)],
    sort(T, NewAcc);

sort([], Acc) ->
    Acc;

Several auxiliary definitions allow the insertion of a single element into the appropriate location within a sorted list

<<insertion_sort>>=
sort(H, [AccH | AccT]) when H =< AccH ->
    [H, AccH | AccT];

sort(H, [AccH | AccT]) ->
    [AccH | sort(H, AccT)];

sort(H, []) ->
    [H].

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

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

insertion_sort
Download code
hijacker
hijacker
hijacker
hijacker