Le tri par bulles est assez ennuyeux, mais il devient plus intéressant si vous essayez de l’implémenter dans un langage fonctionnel pour les télécommunications – c’est à dire. Erlang.
Nous avons une liste de numéros, nous devons la trier. L’algorithme de tri à bulles parcourt toute la liste, en itérant et en comparant les nombres par paires. Lors de la vérification, ce qui suit se produit : un nombre plus petit est ajouté à la liste de sortie, ou les nombres sont intervertis dans la liste actuelle s’il y en a moins à droite, la recherche continue avec le numéro suivant dans l’itération ; Ce parcours est répété jusqu’à ce qu’il n’y ait plus de remplacements dans la liste.
En pratique, cela ne vaut pas la peine d’être utilisé en raison de la grande complexité temporelle de l’algorithme – O(n^2); Je l’ai implémenté en Erlang, dans le style impératif, mais si vous êtes intéressé, vous pouvez rechercher de meilleures 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 et lancement
Dans Ubuntu, Erlang est très facile à installer ; il suffit de taper sudo apt install erlang dans le terminal. Dans ce langage, chaque fichier doit être un module, avec une liste de fonctions pouvant être utilisées en externe – exporter. Les fonctionnalités intéressantes du langage incluent l’absence de variables, uniquement des constantes, l’absence de syntaxe standard pour la POO (ce qui n’empêche pas l’utilisation de techniques de POO), et bien sûr des calculs parallèles sans verrous basés sur le modèle d’acteur.
Vous pouvez exécuter le module soit via la console erl interactive, en exécutant une commande après l’autre, soit plus simplement via l’escript bubbleSort.erl ; Dans différents cas, le fichier aura un aspect différent, par exemple, pour escript, vous devez créer une fonction principale à partir de laquelle il démarrera.
Sources
https://www.erlang.org/
https://habr.com/ru/post/197364/
Code source
https://gitlab.com/ demensdeum/algorithms/blob/master/bubbleSort/bubbleSort.erl
