Kapitel 6: Sortieralgorithmen Flashcards
Was ist internes sortieren ?
Sortieren von Daten im Hauptspeicher, direkter Zugriff
was ist externes sortieren ?
Sortieren von Dateien auf externen Datenträger, sequentieller Zugriff
Was ist Stabilität ?
Bei gleichen Schlüsseln (Duplikaten) bleibt die Reihenfolge der Objekte erhalten
Was ist natürliches Verhalten ?
Bei bereits (weitgehend) sortierter Ausgangsfolge ist die Ausführungszeit am geringsten.
Was ist Insertion Sort ?
Das 1. Element der umsortieren Teilfolge (index i) anschauen und in sortierte Teilfolge einsetzen (an die richtige Stelle (von rechts nach links geschaut))
Weist Insertion Sort Stabilität auf ?
Ja
Weist Insertion Sort ein natürliches Verhalten auf ?
Ja
Was ist Selection Sort ?
Suche in der unsortierten TF das Minimum und vertausche das Minimum mit dem 1. Platz der unsortierten TF
Weist Selection Sort Stabilität auf ?
Nein
Weist Selection Sort ein natürliches Verhalten auf ?
Nein
Wann ist Selection Sort Empfehlenswert ?
Bei teuren Bewegungen der Daten
Wann ist Insertion Sort Empfehlenswert ?
Bei kleinen Eingabefolgen (n<100)
Was ist BubbleSort ?
Starte am Ende der Folge und vertausche benachbarte Elemente. Die jeweils kleineren Elemente steigen nach oben bzw. vorne im Array und das Minimum der unsortierten Teilfolge bis zur 1. Position der Unsortierten Teilfolge.
Weist BubbleSort Stabilität auf ?
Ja
Weist BubbleSort ein natürliches Verhalten auf ?
Bei den Vergleichen nicht, bei den Bewegungen schon.
Insertion Sort Aufwand Vergleiche
Vmin = O(n) Vavg = O(n^2/4) VMax = O(n^2/2)
Selection Sort Aufwand Vergleiche
Vmin = O(n^2/2) Vavg = O(n^2/2) VMax = O(n^2/2)
Bubble Sort Aufwand Vergleiche
Vmin = O(n^2/2) Vavg = O(n^2/2) VMax = O(n^2/2)
Insertion Sort Aufwand Bewegungen
Bmin = O(3n) Bavg = O(n^2/4) Bax = O(n^2/2)
Selection Sort Aufwand Bewegungen
Bmin = O(3n) Bavg = O(3n) Bax = O(3n)
Bubble Sort Aufwand Bewegungen
Bmin = 0 Bavg = O(3n^2/4) Bax = O(3n^2/2)
Was ist Shell Sort ?
Mit einem (anfangs größtmöglichen) gap werden die Elemente verglichen. Gap wird anschließend immer halbiert (Insertion Sort)
Was wendet Shell Sort auch noch an ?
Insertion Sort
Weist Shell Sort Stabilität auf ?
Nein
Weist Shell Sort ein natürliches Verhalten auf ?
Ja wenn Teilfolgen im Abstand GAP teilweise sortiert sind
Was ist Merge Sort ?
Aufteilen einer Folge in Teilfolgen (bis TF nurnoch 1 Element beinhalten). TF werden anschließend Gemerged und dabei sortiert
Weist Merge Sort Stabilität auf ?
Ja
Weist Merge Sort ein natürliches Verhalten auf ?
Ja
Was ist Quick Sort ?
Pivotelement wird ausgewählt, anschließend werden alle Elemente die kleiner oder größer gleich sind in entsprechende Teilfolgen gepackt. Rekursiv wird QuickSort dann auch auf die TF angewendet.
Was ist der Cross Over Point ?
Der Punkt (n Datensätze) an denen ein Algorithmus schneller ist als ein anderer (sie kreuzen sich)
MinHeap Eigenschaften
- Binärbuam
- Vollständiger Baum
- Schlüssel jeder Knoten <= Schlüssel seiner Kinder
- Kein BST!
HeapSort: Kindknoten zu A[i]:
Linker Knoten = A[2*i+1]
Rechter Knoten = A[2*i+2]
HeapSort: Elternknoten zu A[i]:
A[(i-1)/2]
Was macht der percDown Algorithmus ?
“Durchsickern” der Elemente nach unten
Auf welche Teile des Arrays muss percDown aufgerufen werden ?
A[0..(n-1)/2] also auf die erste Hälfte des Arrays (alles keine Blattknoten)
Was ist Heap Sort ?
Ein Array wird durch den Heap-Aufbau so vorsortiert das alle Knoten nurnoch kleinere oder größere (min/max heap) Nachfolger haben.
Anschließend wird von jedem heap sortiert.
Weist Heap Sort Stabilität auf ?
Nein
Weist Heap Sort ein natürliches Verhalten auf ?
Ja
Was liefert eine absteigende Sortierung, Min- oder Max-Heap ?
Min-Heap
