Photoshop
Cinema 4d
HTML / CSS
JavaScript
PHP
Flash
Fotografie
Terragen
Webserver
Informatik
Sonstige
Mergesort (Informatik Tutorial)
Tutorial erstellt von Manuel, letzte Änderung am 21.10.2007
Erklärung:
Mergesort zerteilt das Array rekursiv in möglichst gleich große Teile, bis jedes Teil nur noch ein Element enthält.
Danach werden diese Elemente wieder zusammen gemischt. Daher ähnelt es sehr dem Quicksort-Verfahren.
Nehmen wir hierzu die vorletzte Reihe des folgenden Beispiels. Zuerst wird die 2 mit der 1 verglichen.
Da 1 < 2 wird die 1 in die letzte Zeile geschrieben. Danach wird die 2 mit der 3 verglichen. Da 2 < 3 wird
die 2 in das Array geschrieben usw. Dieser Vorgang wiederholt sich so lange bis kein Element mehr vorhanden ist.
Beispiel:
Aufwand:
Mergesort benötigt bei einem durchschnittlichen Datensatz eine Zeitkomplexität von O(n log n) und ist damit ein optimaler Algorithmus für das Sortierproblem.
>> Allgemeine Fragen oder Probleme mit dem Tutorial? Hier gehts zum Forum!
Mergesort zerteilt das Array rekursiv in möglichst gleich große Teile, bis jedes Teil nur noch ein Element enthält.
Danach werden diese Elemente wieder zusammen gemischt. Daher ähnelt es sehr dem Quicksort-Verfahren.
Nehmen wir hierzu die vorletzte Reihe des folgenden Beispiels. Zuerst wird die 2 mit der 1 verglichen.
Da 1 < 2 wird die 1 in die letzte Zeile geschrieben. Danach wird die 2 mit der 3 verglichen. Da 2 < 3 wird
die 2 in das Array geschrieben usw. Dieser Vorgang wiederholt sich so lange bis kein Element mehr vorhanden ist.
Beispiel:
Aufwand:
Mergesort benötigt bei einem durchschnittlichen Datensatz eine Zeitkomplexität von O(n log n) und ist damit ein optimaler Algorithmus für das Sortierproblem.
>> Allgemeine Fragen oder Probleme mit dem Tutorial? Hier gehts zum Forum!
