Scribd
Hochladen
14 Ansichten13 Seiten

Heapsort

Heapsort ist ein effizienter, vergleichsbasierter Sortieralgorithmus, der auf der Datenstruktur Heap basiert und 1964 von Robert W. Floyd und J.W. Williams entwickelt wurde. Der Algorithmus nutzt die Eigenschaften von Min- und Max-Heaps, um Daten zu sortieren, indem er die Heap-Bedingungen prüft und die Elemente entsprechend anordnet. Die Zeitkomplexität von Heapsort variiert je nach Fall (Best-, Average- und Worst-Case) und die Stabilität des Algorithmus wird ebenfalls thematisiert.

Hochgeladen von

gutmannjaime
Copyright
© All Rights Reserved
Wir nehmen die Rechte an Inhalten ernst. Wenn Sie vermuten, dass dies Ihr Inhalt ist, beanspruchen Sie ihn hier.
Verfügbare Formate
Als PDF, TXT herunterladen oder online auf Scribd lesen
14 Ansichten13 Seiten

Heapsort

Heapsort ist ein effizienter, vergleichsbasierter Sortieralgorithmus, der auf der Datenstruktur Heap basiert und 1964 von Robert W. Floyd und J.W. Williams entwickelt wurde. Der Algorithmus nutzt die Eigenschaften von Min- und Max-Heaps, um Daten zu sortieren, indem er die Heap-Bedingungen prüft und die Elemente entsprechend anordnet. Die Zeitkomplexität von Heapsort variiert je nach Fall (Best-, Average- und Worst-Case) und die Stabilität des Algorithmus wird ebenfalls thematisiert.

Hochgeladen von

gutmannjaime
Copyright
© All Rights Reserved
Wir nehmen die Rechte an Inhalten ernst. Wenn Sie vermuten, dass dies Ihr Inhalt ist, beanspruchen Sie ihn hier.
Verfügbare Formate
Als PDF, TXT herunterladen oder online auf Scribd lesen

HEAPSORT

Heapsort Allgemeines

- effizienter, vergleichsbasierter Sortieralgorithmus

- Ist eine Weiterentwicklung des Selectionsort

- 1964 von Robert W. Floyd und J.W Williams entwickelt

- Basiert auf Datenstruktur Heap


Min Heap/ Max
Heap
Bedingung
- Min Heap oder Max Heap
Bedingung muss erfüllt sein

- Bei Max Heap muss Wert des


Elternknoten grösser oder gleich
gross wie der des Kindknoten sein

- Beim Min Heap genau umgekehrt


Datenstruktur
Heap

- Datenstruktur zum Sortieren von


Daten
- Lässt sich durch Binärbaum
darstellen

- Baum wächst von links nach rechts


und von oben nach unten
- Dabei darf jeder Knoten höchstens
zwei Kindknoten haben
Beispiel (heapify)

- Array (7, 3, 9, 2, 1, 4)

- Sollen mit Max Heap sortiert


werden

- Heap Bedingung prüfen


Beispiel (heapify)

- Heap Bedingung erfüllt

- 9 wird mit letzter Zahl getauscht

- 9 endgültig sortiert kann ignoriert


werden

- 4 wird zur neuen Wurzel


Beispiel

- 7 mit 4 Tauschen

- 1 wird zur neuen Wurzel

- Array am Schluss (1,2,3,4,7,9)


Code
− heapsort(Array A) #Heapsort auf A anwenden

− build(A) #A wird zu MaxHeap umgewandelt

− assert(isHeap(A, 0)) #überprüft Korrektheit des Heaps

− tmp = [Link] #grösse von A zwischenspeichern

− while ([Link] > 1) #Bedingung wann zu stoppen ist

− [Link](0, [Link] - 1) #wechselt erste und letzte Stelle


[Link] = [Link] - 1 #sortierte Ziffer wird ignoriert
heapify(A) #oben erwähnter Vorgang
assert(isHeap(A, 0)) #überprüft Korrektheit des Heaps

Befehl − [Link] = tmp #grösse von A zurücksetzen


Variable
Bedingung assert(isSorted(A)) #überprüft Korrektheit der Sortierung
Zahlen
Sonstiges
0

1 2

3 4 5 6
6

1 2

3 4 5 0
Zeitkomplexität

- Best-Case Komplexität

- Average-Case Komplexität

- Worst-Case Komplexität

- Begründung
o Höhe des Heaps
o Heap-Aufbau
o Sortierphase

- Beispiel
Stabilität

- Erklärung

- Stabilität von Heapsort


FRAGEN?

Das könnte Ihnen auch gefallen