Bubble sort (Erlang)
From LiteratePrograms
On each comparison step we'll need 3 variables: for the part processed on the current pass, yet unprocessed part, and a flag, whether there were transpositions of the current pass, that is whether sorting should stop after the current pass.
So we redefine the basic call to use the notation with three arguments. At the beginning, we have no transpositions, so halting flag is true.
<<bubblesort.erl>>= -module(bubblesort). -export([sort/1]). -import(lists, [reverse/1]). sort(L) -> sort(L, [], true).
If we have no items in the unprocessed list, we return the resulting list, if there were no transpositions during the last pass, else we start the next pass. Note, that since we're going to add items to the head of the resulting list, it is reversed and we must reverse it back before returning it or starting the next pass.
<<bubblesort.erl>>= sort([], L, true) -> reverse(L); sort([], L, false) -> sort(reverse(L), [], true);
If unprocessed part contains two or more items and the first item is greater than the second, then we add the second item to the head of the resulting list, leaving the first in the head of the unprocessed list, and set the halting flag to false, since we're changing the order of items in the resulting list.
<<bubblesort.erl>>= sort([ X, Y | T ], L, _) when X > Y -> sort([ X | T ], [ Y | L ], false);
Else we just add the first item in the unprocessed list to the head of the resulting list, passing the halting flag through.
<<bubblesort.erl>>= sort([ X | T ], L, Halt) -> sort(T, [ X | L ], Halt).