Bubble Sort in Erlang

Bubble sort is pretty boring, but it becomes more interesting if you try to implement it in a functional language for telecom – Erlang.

We have a list of numbers, we need to sort it. The bubble sort algorithm goes through the entire list, iterating and comparing numbers in pairs. During the check, the following happens: the smaller number is added to the output list, or the numbers are swapped in the current list; if there is less on the right, the iteration continues with the next number in the iteration. This iteration is repeated until there are no more replacements in the list.

In practice, it is not worth using because of the high time complexity of the algorithm – O(n^2); I implemented it in Erlang, in an imperative style, but if you are interested, you can look for better options:

-module(bubbleSort).
-export([main/1]).

startBubbleSort([CurrentHead|Tail]) ->
    compareHeads(CurrentHead, Tail, [], [CurrentHead|Tail]).

compareHeads(CurrentHead, [NextHead|Tail], [], OriginalList) ->   
    if
        CurrentHead < NextHead ->
            compareHeads(NextHead, Tail, [CurrentHead], OriginalList);
        true ->
            compareHeads(CurrentHead, Tail, [NextHead], OriginalList)
    end;
    
compareHeads(CurrentHead, [NextHead|Tail], OriginalOutputList, OriginalList) ->
    if
        CurrentHead < NextHead ->
            OutputList = OriginalOutputList ++ [CurrentHead],
            compareHeads(NextHead, Tail, OutputList, OriginalList);
        true ->
            OutputList = OriginalOutputList ++ [NextHead],
            compareHeads(CurrentHead, Tail, OutputList, OriginalList)
    end;
  
compareHeads(CurrentHead, [], OriginalOutputList, OriginalList) ->
    OutputList = OriginalOutputList ++ [CurrentHead],
    if
        OriginalList == OutputList ->
            io:format("OutputList: ~w~n", [OutputList]);
        true ->
            startBubbleSort(OutputList)
    end.
  
main(_) ->
    UnsortedList = [69,7,4,44,2,9,10,6,26,1],
    startBubbleSort(UnsortedList).

Installation and launch

In Ubuntu, Erlang is very easy to install, just type sudo apt install erlang in the terminal. In this language, each file must be a module, with a list of functions that can be used from the outside – export. Interesting features of the language include the absence of variables, only constants, the absence of standard syntax for OOP (which does not prevent the use of OOP techniques), and of course parallel computations without locks based on the actor model.

You can launch the module either through the interactive console erl, running one command after another, or more simply through escript bubbleSort.erl; The file will look different for different cases, for example, for escript you need to make a main function from which it will start.

Sources

https://www.erlang.org/
https://habr.com/ru/post/197364/

Source code

https://gitlab.com/ demensdeum/algorithms/blob/master/bubbleSort/bubbleSort.erl