Einfügungssortierung
Einfügesortierung – Jedes Element wird mit den vorherigen Elementen in der Liste verglichen und das Element wird mit dem größeren ausgetauscht, falls vorhanden, andernfalls die innere Vergleichsschleife stoppt. Da die Elemente vom ersten bis zum letzten sortiert werden, wird jedes Element mit einer bereits sortierten Liste verglichen, was *möglicherweise* die Gesamtlaufzeit verkürzt. Die zeitliche Komplexität des Algorithmus beträgt O(n^2), also identisch mit der Blasenvariante.
Sortierung zusammenführen
Sortierung zusammenführen – Die Liste wird in Gruppen eines Elements unterteilt. Anschließend werden die Gruppen paarweise „zusammengeführt“ und gleichzeitig verglichen. In meiner Implementierung werden beim Zusammenführen von Paaren die Elemente auf der linken Seite mit den Elementen auf der rechten Seite verglichen und dann in die resultierende Liste verschoben. Wenn die Elemente auf der linken Seite nicht mehr vorhanden sind, werden alle Elemente auf der rechten Seite zur Ergebnisliste hinzugefügt Liste (ihr zusätzlicher Vergleich ist unnötig, da alle Elemente in den Gruppen Sortieriterationen durchlaufen)< br />Die Arbeit dieses Algorithmus lässt sich sehr einfach parallelisieren; die Phase der Zusammenführung von Paaren kann in Threads durchgeführt werden, wobei auf das Ende der Iterationen im Dispatcher gewartet wird.
Ausgabe des Algorithmus für Single-Threaded-Ausführung:
["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", "Артем"]
Ausgabe des Algorithmus für die Multithread-Ausführung:
["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", "Артем"]
Die zeitliche Komplexität des Algorithmus beträgt O(n*log(n)), was etwas besser ist als O(n^2)
Quellen
https://en.wikipedia.org/wiki/Insertion_sort
https://en.wikipedia.org/wiki/Merge_sort
Quellcode
https://gitlab.com/demensdeum /algorithms/-/tree/master/sortAlgorithms/insertionSort
https://gitlab.com/demensdeum/algorithms/-/tree/master/sortAlgorithms/mergeSort