Selection sort (Erlang)
From LiteratePrograms
On each step of selection sort we'll need two variables: the rest of the list to be sorted and the already sorted list. Our module exports sort with one argument, so we define it with the internal 2-arguments function.
<<selectionsort.erl>>= -module(selectionsort). -export([sort/1]). sort(L) when is_list(L) -> sort(L, []).
We end up when the unsorted list is empty. Note, that we need to reverse the sorted list, because we'll add elements to its head.
<<selectionsort.erl>>= sort([], L) -> lists:reverse(L);
If there's something in the unsorted list, we remove the least item from there and add it to the head of the sorted list, and then do tail-recursion.
<<selectionsort.erl>>= sort(L, Sorted) -> {Min, Rest} = remove_min(L), sort(Rest, [Min | Sorted]).
Selecting function
Now it's time to define the function which removes the least item from the list. In naïve implementation (the very one we're making) it finds the least element by traversing all items (if you want to know how to do it less naïve way, check out heapsort, for instance).
We'll need 3 variables here: the list of yet not checked items, the minimum found value and the list of already checked items. First of all, we define the terse one-argument function with its 3-arguments namesake. We suppose the first element is the least, and the list of checked items is empty.
Warning: The next implementation of remove_min function makes sort unstable.
<<selectionsort.erl>>= remove_min([H | T]) -> remove_min(T, H, []).
If there are no unchecked items, it means we've got the minimum value and the rest of the list and we can halt.
<<selectionsort.erl>>= remove_min([], Min, Rest) -> { Min, Rest };
If we've found the lesser item in the list, we must make it the new mininum and add the old minimum to the list of checked items.
<<selectionsort.erl>>= remove_min([H | T], Min, Rest) when H < Min -> remove_min(T, H, [Min | Rest]);
Else we just put the first item to the list of checked items.
<<selectionsort.erl>>= remove_min([H | T], Min, Rest) -> remove_min(T, Min, [H | Rest]).
Stable sort
To make the sort stable, we should change the definition of remove_min function. We'll redefine it through remove_rmin function, which returns the rightmost minimum value in the list.
This program is a code dump.
Code dumps are articles with little or no documentation or rearrangement of code. Please help to turn it into a literate program. Also make sure that the source of this code does consent to release it under the MIT or public domain license.
<<selectionsort2.erl>>= -module(selectionsort). -export([sort/1, remove_min/1, remove_rmin/1]). sort(L) when is_list(L) -> sort(L, []). sort([], L) -> lists:reverse(L); sort(L, Sorted) -> {Min, Rest} = remove_min(L), sort(Rest, [Min | Sorted]). remove_min(L) -> {Min, Rest} = remove_rmin(lists:reverse(L)), {Min, lists:reverse(Rest)}. remove_rmin([H | T]) -> remove_rmin(T, H, []). remove_rmin([], Min, Rest) -> { Min, lists:reverse(Rest) }; remove_rmin([H | T], Min, Rest) when H =< Min -> remove_rmin(T, H, [Min | Rest]); remove_rmin([H | T], Min, Rest) -> remove_rmin(T, Min, [H | Rest]).
| Download code |