Die Funktion Sort

Vorherige Seite Inhaltsverzeichnis Nächste Seite

sort in Struktur

  • Kurzbeschreibung
  • Schnittstelle
  • Parameter
  • Vorbedingung
  • Nachbedingung
  • Realisierung
  • Hilfsfunktionen
  • Aufgabe
  • Bedienungstipps
  • Das Applet
  • Lösung

  • Kurzbeschreibung

    Verschiebt alle Schlüssel des Heapbaums in die Ergebnisliste.

    Schnittstelle

    Parameter

    Explizite Parameter: - (Keine).
    Implizite Parameter: Heapbaum, Ergebnisliste

    Vorbedingung

    Heapbaum: vollständig, voll gefüllt und heapgeordnet.
    Ergebnisliste: leer.

    Sort Start
    Knoten Bedeutung
    Grüner Knoten Erfüllt die Heapbedingung.
    Leerer Knoten Leer.

    Nachbedingung

    Heapbaum leer. Ergebnisliste aufsteigend geordnet und voll gefüllt.

    Sort Goal
    Knoten Bedeutung
    Leerer Knoten Leer.
    Schlüssel Knoten Größe des Schlüssels.

    Realisierung

    Hilfsfunktionen

    Funktion (Parameter) Kurzbeschreibung Vorbedingung
    Move-Max () Verschiebt den maximalen Schlüssel des Heapbaums in die Ergebnisliste. Heapbaum: vollständig und heapgeordnet.
    Ergebnisliste: aufsteigend geordnet.

    Aufgabe

    Verschieben Sie alle Schlüssel in die Ergebnisliste.

    Bedienungstipps

    Das Applet

    Fehler: Ihr Browser unterstützt kein JAVA!

    Lösung

    Erlaubte Reihenfolgen: Für diese Funktion gibt es nur eine mögliche Reihenfolge.

    Das Standardverfahren: Move-Max wird so oft aufgerufen, wie Schlüssel im Heapbaum sind. Es entnimmt jeweils den maximalen Schlüssel aus dem Heapbaum und fügt ihn vorne an die Elemente der Ergebnisliste an. Dadurch entsteht eine aufsteigend sortierte Liste.

    Laufzeit: Move-Max-Aufrufe: Anzahl Schlüssel.

    Korrektheit: Folgt aus der Korrektheit von Move-Max.


    Vorherige Seite Inhaltsverzeichnis Nächste Seite