Bubble Sort ist ziemlich langweilig, aber es wird interessanter, wenn Sie versuchen, es in einer funktionalen Sprache für die Telekommunikation zu implementieren – Erlang.
Wir haben eine Liste mit Zahlen, wir müssen sie sortieren. Der Blasensortierungsalgorithmus durchläuft die gesamte Liste und iteriert und vergleicht die Zahlen paarweise. Bei der Prüfung geschieht Folgendes: Eine kleinere Zahl wird zur Ausgabeliste hinzugefügt, oder die Zahlen werden in der aktuellen Liste vertauscht, wenn rechts weniger vorhanden sind, wird die Suche mit der nächsten Zahl in der Iteration fortgesetzt. Dieser Durchlauf wird wiederholt, bis die Liste keine Ersetzungen mehr enthält.
In der Praxis lohnt sich der Einsatz aufgrund der hohen zeitlichen Komplexität des Algorithmus nicht – O(n^2); Ich habe es in Erlang im Imperativstil implementiert, aber wenn Sie interessiert sind, können Sie nach besseren Optionen suchen:
-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 und Start
In Ubuntu ist Erlang sehr einfach zu installieren; geben Sie einfach sudo apt install erlang in das Terminal ein. In dieser Sprache muss jede Datei ein Modul sein, mit einer Liste von Funktionen, die extern verwendet werden können – Export. Zu den interessanten Merkmalen der Sprache gehören das Fehlen von Variablen, nur Konstanten, das Fehlen einer Standardsyntax für OOP (was die Verwendung von OOP-Techniken nicht verhindert) und natürlich parallele Berechnungen ohne Sperren basierend auf dem Akteurmodell.
Sie können das Modul entweder über die interaktive ERL-Konsole ausführen, indem Sie einen Befehl nach dem anderen ausführen, oder einfacher über escript bubbleSort.erl; In verschiedenen Fällen sieht die Datei anders aus, zum Beispiel müssen Sie für escript eine Hauptfunktion erstellen, von der aus sie gestartet wird.
Quellen
https://www.erlang.org/
https://habr.com/ru/post/197364/
Quellcode
https://gitlab.com/ demensdeum/algorithms/blob/master/bubbleSort/bubbleSort.erl
