|
|
Definition bzw. Erklärung: Heapsort
|
|
|
|
|
Bei dem Begriff Heapsort handelt es sich um einen im Jahr 1964 von J. Williams
entwickelten schnellen Algorithmus zur Sortierung von Daten.
Beim Heapsort wird der Datenbestand in einem binären Baum, also in eine
Verästelungsstruktur, in der jeder Knoten maximal 2 Äste hat, umgewandelt.
Dann werden, beginnend von unten nach oben und von links nach rechts die Elemente
der einzelnen Äste paarweise so vertauscht, dass sich das jeweils größte Element
im Knotenpunkt befindet, bis das größte Element des kompletten Datenbestands ganz oben in
der Baumstruktur steht. Dieses wird daraufhin entfernt und das am weitesten rechts stehende
Element der untersten Ebene rutscht nach oben nach. Dieser Vorgang wird solange wiederholt, bis
der Baum abgebaut it, und damit alle Elemente sortiert sind. Diese Art der Sortierung gehört mit
zu den schnellsten, ist jedoch im Durchschnitt einwenig langsamer als der Quicksort-Algorithmus.
|
|
|
|
|
|
© 2003-2012 Alle Texte, Grafiken sowie das Design sind Urheberrechtlich geschützt und
dürfen nicht ohne Zustimmung von Bullhost Internet Service weiter verwendet werden.
|
|
|
|
Informationen