Tri par insertion
Tri par insertion – chaque élément est comparé aux précédents de la liste et l’élément est échangé avec le plus grand, le cas échéant, sinon la boucle de comparaison interne s’arrête. Étant donné que les éléments sont triés du premier au dernier, chaque élément est comparé à une liste déjà triée, ce qui *éventuellement* réduit le temps d’exécution global. La complexité temporelle de l’algorithme est O(n^2), c’est-à-dire identique à la variété des bulles.
Fusionner le tri
Tri par fusion – la liste est divisée en groupes d’un élément, puis les groupes sont « fusionnés » par paires avec comparaison simultanée. Dans mon implémentation, lors de la fusion de paires, les éléments de gauche sont comparés aux éléments de droite, puis déplacés vers la liste résultante si les éléments de gauche ont disparu, alors tous les éléments de droite sont ajoutés à la liste résultante ; liste (leur comparaison supplémentaire est inutile, puisque tous les éléments des groupes passent par des itérations de tri)< br />Le travail de cet algorithme est très simple à paralléliser ; l’étape de fusion des paires peut être effectuée en threads, en attendant la fin des itérations dans le répartiteur.
Résultat de l’algorithme pour l’exécution monothread :
["John", "Alice", "Mike", "#1", "Артем", "20", "60", "60", "DoubleTrouble"]
[["John"], ["Alice"], ["Mike"], ["#1"], ["Артем"], ["20"], ["60"], ["60"], ["DoubleTrouble"]]
[["Alice", "John"], ["#1", "Mike"], ["20", "Артем"], ["60", "60"], ["DoubleTrouble"]]
[["#1", "Alice", "John", "Mike"], ["20", "60", "60", "Артем"], ["DoubleTrouble"]]
[["#1", "20", "60", "60", "Alice", "John", "Mike", "Артем"], ["DoubleTrouble"]]
["#1", "20", "60", "60", "Alice", "DoubleTrouble", "John", "Mike", "Артем"]
Sortie de l’algorithme pour l’exécution multithread :
["John", "Alice", "Mike", "#1", "Артем", "20", "60", "60", "DoubleTrouble"]
[["John"], ["Alice"], ["Mike"], ["#1"], ["Артем"], ["20"], ["60"], ["60"], ["DoubleTrouble"]]
[["20", "Артем"], ["Alice", "John"], ["60", "60"], ["#1", "Mike"], ["DoubleTrouble"]]
[["#1", "60", "60", "Mike"], ["20", "Alice", "John", "Артем"], ["DoubleTrouble"]]
[["DoubleTrouble"], ["#1", "20", "60", "60", "Alice", "John", "Mike", "Артем"]]
["#1", "20", "60", "60", "Alice", "DoubleTrouble", "John", "Mike", "Артем"]
La complexité temporelle de l’algorithme est O(n*log(n)), ce qui est légèrement meilleur que O(n^2)
Sources
https://en.wikipedia.org/wiki/Insertion_sort
https://en.wikipedia.org/wiki/Merge_sort
Code source
https://gitlab.com/demensdeum /algorithms/-/tree/master/sortAlgorithms/insertionSort
https://gitlab.com/demensdeum/algorithms/-/tree/master/sortAlgorithms/mergeSort