Informatik 2.5 Sortierverfahren PDF

Preview

Summary

SoSe18...

Description

Sortieralgorithmen Übersicht Einführung Einfache Verfahren Mergesort Untere Schranke Einführung -

Statisches Wörterbuch:

-Lösungsmöglichkeiten: Hashing: Suche in konstanter Zeit Ordnung auf Elemente, d.h. Bereichsanfrage die mit `A` anfangen) aufwändig

1.Perfektes -Vorteil: -Nachteil: keine (z.B. alle Namen,

2.Speicherung der Daten in sortiertem Feld -Vorteil: Bereichsanfragen möglich -Nachteil: Suche insgesamt teurer (logarithmische Zeitkomplexität) -

Sortierproblem: Prämisse: Existierende Ordnung ≤ auf der Menge der Schlüssel Eingabe: Sequenz s= ⟨ e1,..,en ⟩ Beispiel: Ausgabe: Permutation s‘=(e‘1,..,e’n) von s, so dass key(e‘1) ≤ key(e’i+1) für ∀i∈ {1,. . ,n } Beispiel:

-

Eigenschaften von Sortierverfahren: -

Vorteile/Nachteile von Sortierverfahren: -Eingabe: vorsortierte Sequenzen -Datenstrukturen: Sortieren auf Feldern oder Listen

-

Ex-situ vs. in-situ-Sortierung (z.B. bei Feldern)

Einfache Verfahren  SelectionSort  Insertionsort SelectionSort:

-

 Sortieren durch Auswählen (in-situ)  Wähle das kleinste Element aus der verbleibenden Eingabesequenz und verschieben es an das Ende der Ausgabesequenz

Zeitaufwand:     -

Minimumsuche in Feld der Größe i: Θ (i) n−1 Θ (i)= Θ (n2) Gesamtzeit: Σ ⅈ=0 Vorteil: einfach zu implementieren Nachteil: quadratische Laufzeit

InsertionSort:  Nimm ein Element aus der Eingabesequenz und füge es an der richtigen Stelle in die Ausgabesequenz ein

Zeitaufwand:  Minimumsuche in Feld der Größe i: O(i) n−1

 Gesamtzeit:

∑ O ( ⅈ ) = O(n2) i=0

 Vorteil: einfach zu implementieren  Nachteil: quadratische Laufzeit

-

Einfache Verfahren – Übersicht:

 BubbleSort o Sehr viele Vergleiche durch Tausch über ganze Struktur O(n2)  SelectionSort n

o mit besserer Minimumstrategie worst case Laufzeit n log ¿ erreichabr O¿

 InsertionSort n

o mit besserer Einfügungsstrategie worst case Laufzeit O¿ log2 n) erreichbar  ShellSort  bestmöglichste untere Schranke

MergeSort  Sortieren durch Verschmelzen  Zerlege die Eingabesequenz rekursiv in Teile, die separat sortiert und dann zur Ausgabesequenz verschmolzen werden

Zeitaufwand:  T(n): Laufzeit bei Feldgröße n  T(1) = Θ (1)  T(n) = T( ⌈ n ∕ 2⌉ ) + T( ⌊ n ∕ 2 ⌋ ) + Θ (n)  T(n) ∈ O(n log n) (folgt aus dem Master-Theorem)

Maste-Theorem und Aufwandbestimmung für Rekursion:

-

Analyse rekursiver Funktionen – Divide & Conquer Algorithmen  Bisher: einfache und separate Analyse nichtrekursiver Funktionsaufrufe  Hier: rekursive Aufrufstrukturen erzeugen Rekursionsgleichungen  Abstieg mit kleineren Argument bestimmt Funktionswert  Ziel: finde hierfür eine nichtrekursive /geschlossene Form  Anwendung: Divide-and-Conquer-Algorithmen o gegeben: Problem der Größe n=bk (k ∈ N0) o falls k=0 bzw. n=1: löse das Problem mit Aufwand a o falls k≥1: 1. Zerlege das Problem in d Teilprobleme der Größe n/b 2. Löse die Teilprobleme (d.h. d rekursive Aufrufe) 3. Setze aus den Teillösungen die Lösung zusammen  Notation o a sei der Aufwand zum Lösen des Problems auf Rekursionsstufe k=0 o b sei die Basisgröße des Problems (Annahme: n=bk) o c sie die Arbeit zum Aufteilen und Zusammensetzen der Lösung o d sei die Anzahl der Teilprobleme einer Rekursionsstufe  Prinzip: Betrachte den Aufwand für jede Rekursionstiefe  Anfang: Problemgröße n  Bei Rekursionstiefe i: di Teilprobleme der Größe n/bi  Gesamtaufwand bis zur Rekursionsstufe i:

- db

Aufwand steigt mit wachsender Rekursionstiefe; letztes Level entspricht konstantem Anteil des Gesamtaufwandes

Untere Schranke – Vergleichsbasiertes Sortieren...