Vorlesung 05 - Sortierverfahren PDF

Preview

Summary

Zusammenfassung Kapitel 5 ADS...

Description

// ADS_Sortier-Algortihmen Allgemeines: Eine Menge von Objekten (d) mit Schlüsselwerten (k) und Ordnungsrelation (f)

Kriterien zur Bewertung von Suchalgortihmen + Ausführungszeit – Zugriffszeit – Anzahl der Vergleiche – Anzahl der Vertauschungen - Speicherplatz • Algorithmus benötigt Speicherplatz für Objekte und Hilfsstruktur - Stabilität: • Bei gleichen Schlüsseln bleibt die Reihenfolge der Objekte erhalten - Natürliches Verhalten: • Bei bereits (weitgehend) sortierter Ausgangsfolge ist die Ausführungszeit am geringsten Laufzeiten: Insertionsort: O(n^2) Shellsort: O(n log2n) Mergesort: O(n log2n) Quicksort: O(n log2n) Heapsort: O(n log2n) Definition 5.1: Sortieren Anordnung der Objekte in einer Folge derart, daß für zwei beliebige Objekte: Objekt di mit Schlüssel kiund Objekt dj mit Schlüssel kj in der Folge gilt: f(k) = f(kj) bei Sortierung in aufsteigender Reihenfolge bzw.f(ki) = f(kj) bei Sortierung in absteigender Reihenfolge ______________________________________________________________ Insertion Sort (Sortieren durch direktes Einfügen) -Untersuchung der Elemente der Reihe nach - Einfügen des Elementes innerhalb der schon untersuchten Elemente an seinem richtigen Platz -( dazu: größere Elemente nach rechts bewegen/ neues Element an frei gewordenem Platz einfügen/ Ende: wenn das letzte Element eingefügt worden ist)

Struktogramm siehe: ADS14K Seite 17

Eigenschaften von Insertion Sort -Stabil: Bei gleichen Schlüsseln bleibt die Reihenfolge der Objekte erhalten -natürliches Verhalten: geringste Ausführungszeit bei vorsortierten Mengen ______________________________________________________________ Selection Sort (Sortieren durch direkte Auswahl) -Suche von allen Elementen das kleinste Element -Tausche das kleinste Element mit dem 1.Platz -Suche von den N-1 verbleibenden Elemten das nächst kleinste Element -Tausche das 2. kleinste Element mit dem 2.Platz -Wiederhole die Schritte 3 und 4 mit den weiteren Elementen, bis schließlich das vorletzte mit dem letzten Element verglichen wird i = 1 bis N-1 Durchläufe Elemente a[0] bis a[i-1] sind sortiert im Durchlauf : Suche das kleinste Element a[min] aus der Folge a[i] bis a[N-1] tausche das kleinste Element a[min] mit a[i] Struktogramm siehe: ADS14K Seite 28

Eigenschaften von Selecetion Sort -Stabil -zeigt bei den Vergleichen weniger natürliches Verhalten als Insertion Sort -Empfehlung: Insertion Sort ist bei kleinen Datensätzen vorzuziehen Selection Sort ist bei teureren Bewegungen der Datensätze vorzuziehen! ______________________________________________________________ Bubble Sort (Sortieren durch direkten Austausch) -Beginne mit dem (n-1)-ten Feldelement. -Vergleiche benachbarte Elemente a[i-1] und a[i] und vertausche diese, wenn a[i] < a[i-1] ist -Am Ende von diesem Durchlauf ist das kleinste Element an der Stelle a[0] -Wiederhole die Schritte 1-3 und gehe nur noch bis zur Position, die noch nicht sortiert ist Bubble Sort: Luftblasen aufsteigen lassen! hier: Die kleineren Elemente steigen nach oben und das jeweils kleinste Element an die richtige Position i = 1 bis N-1 Durchläufe Elemente a[0] bis a[i-1] sind sortiert im Durchlauf: Durchsuche benachbarte Elemente a[j] und a[j-1] innerhalb der Folge von a[N-1] bis a[i] und vertausche benachbarte Elemente, wenn a[j]...