Sortieren Flashcards
Test
Wann spricht man von einer partiellen Ordnung R?
- reflexiv: es gilt a R a
- antisymmetrisch: a R b und b R a folgt a = b
- transitiv: a R b und b R c folgt a R c
Wann spricht man von einer totalen Ordnung R?
- R ist partielle Ordnung
- für alle a,b gilt: a R b oder b R a
Wie werden Zugriffsoperationen bei der Laufzeitanalyse beim Sortieren bezeichnet?
c_z
Wie werden Vergleichsoperationen bei der Laufzeitanalyse beim Sortieren bezeichnet?
c_v
Wie werden Datenaustauschsoperationen bei der Laufzeitanalyse beim Sortieren bezeichnet?
c_d
Welche Operationen gibt es beim Sortieren?
- Zugriffsoperation
- Vergleichsoperationen
- Datenaustauschoperationen
Beschreibe in-place Verfahren
Ein Sortieralgorithmus arbeitet ‘in place’, wenn es außer dem zu sortierenden Datenarray nur konstant viel Speicherplatz benötigt.
Wann ist ein Sortierverfahren stabil?
Ein Sortieralgorithmus ist ‘stabil’, wenn bei Gleichheit der zu sortierenden Objekte die Eingabereihenfolge erhalten bleibt
Durch welche Eigenschaften kann man einen Soriteralgorithmus beschreiben?
- Effizienz
- Speicherbedarf
- Stabilität
Welche Laufzeit hat Sortieren durch Auswahl?
Wie funktioniert Sortieren durch Auswahl?
Wie viele Datenaustauschoperationen benötigt man für den Selectionsort?
max. N-1
Ist der Selectionsort stabil und in-place?
Ja, stabil und in-place
Welche Laufzeit Insertionsort?
Ist der Insertionsort in-place und stabil?
Ja, in-place und stabil
Wie funktioniert Sortieren durch Einfügen?
Welche Laufzeit hat der Bubblesort?
Ist der Bubblesort stabil und in-place?
Ja, stabil und in-place
Wie funktioniert der Bubblesort?
Wie funktioniert der Mergesort?
Beschreib den 2-Wege-Merge
Welche Laufzeit hat die Merge Operation?
für die Listen L und R
O(|L|+|R|) = O(N)
Ist die Merge Operation mit Listen stabil und in-place?
Ja, stabil und in-place
Ist die Merge Operation mit Arrays stabil und in-place?
Nein, stabil aber nicht in-place (linear abhängige Arrays als zwischenspeicher)
Welche Laufzeit hat der Mergesort?
Welchen Speicherbedarf hat der Mergesort?
Was passiert mit der Laufzeit, wenn man nicht 2 sondern k Listen bei dem Mergesort verwendet?
Was ist die Heap-Bedingung?
Objekte liegen auf einer Halde, ein Objekt ist immer mindestens so groß wie die darunter liegenden Objekte
Welche Operationen sind auf einem Heap definiert?
- BUILD-MAX-HEAP: baue eine Halde aus
einer Menge von Elementen - HEAP-EXTRACT-MAX: nehme das größte Element von der Halde
- MAX-HEAPIFY: stelle die Heap- Bedingung nach Entnahme wieder her
Auf welche Datenstruktur basiert ein Heap?
Auf einem binären Baum
Was bedeutet linksvollständig?
alle Ebenen bis auf die letzte sind vollständig, in der letzten folgen die Elemente von links nach rechts.
Wie wird ein Heap durch ein Array repräsentiert?
Wie berechnet man den Index des Parent Elements in einem Heap?
Welche Höhe hat ein Heap der Größe N maximal?
Wie berechnet man den Index des Linken Kind Elements in einem Heap?
Wie berechnet man den Index des Rechten Kind Elements in einem Heap?
Wie geht man bei Heapify vor?
Nehme Max Child der kaputten Stelle i und vertausche die Elemente
Wiederhole an der alten Stelle des Max Child falls immer noch kaputt
Welche Laufzeit hat Max-Heapify?
O(log n)
Welche Laufzeit hat Build-Max-Heap?
O(n log n)
Hat man ein unsortiertes Array und möchte ein Heap erstellen, was gilt für den Heap nach dem einfügen der Daten, welche Knoten sind dann auf jeden Fall schon Heaps?
Wie berechnet man den Index des ersten Knotens, der kein Heap darstellt
Die Blätter
Welche Operationen sind auf eine Priority Queue definiert?
Mit welcher Sortierstruktur kann eine Priority Queue realisiert werden?
Durch einen Heap
Wie und für welche Zahlen funktioniert der Counting Sort?
Mit welcher Laufzeit für die Operationen insert, delete, increase, decrease und extract-max kann eine Priority-Queue mit einem Heap realisiert werden?
O(log N)
Wie funktioniert Heap-Increase-Key?
Wie wird der Counting Sort stabil realisiert?
Am Ende den Array von hinten nach vorne durchlaufen
Ist der Counting Sort in-place?
Nein
Wie funktioniert Heap-Insert?
Der Priority-Queue
Wie funktioniert der Quicksort?
Wie funktioniert die Partition Funktion?
Wie funktioniert die Partition Funktion mit nur einer Schleife?
Was ist die Rekurrenzgleichung für Quicksort?
Was ist die Laufzeit vom Quicksort? Pivot-Element liegt in der Mitte
O(N log N)
auch average case
Wie hoch ist mein Rekursionsbaum, wenn der größere Teil immer 9/10 der Daten annimmt?
Was ist die Laufzeit vom Quicksort? (Worst Case)
Pivot ist Maximum
Wie funktioniert der Trivial Sort und für welche Daten?
ganzzahlige Zahlen
Wie und für welche Zahlen funktioniert der Counting Sort?
Laufzeit Trivial Sort?
O(N)
Laufzeit Counting Sort?
Wie wird der Counting Sort stabil realisiert?
Am Ende den Array von hinten nach vorne durchlaufen
Wie wird ein m-adischer Schlüssel repräsentiert?
Durch einen Vektor
Beschreibe den Radix Sort
Laufzeit vom Radix Sort
Fall 1: d= O(1), m = O(N)
O(N)
Laufzeit vom Radix Sort
Fall 2: Alle Schlüssel verschieden: d ≥ log_m N :
O(N log N)
Ist der Radix Sort stabil / in-place?
stabil, aber nicht in-place
Ist der Counting Sort stabil / in-place?
stabil, aber nicht in-place
Ist der Trivial Sort stabil / in-place?
stabil und in-place
Beschreibe den Bucketsort
Laufzeit Bucketsort
(Worst Case)
O(N^2)
Laufzeit Bucketsort
(Average Case)
O(N)
Welche Laufzeit hat eine binäre Suche?
O(log N)
Beschreibe die Exponentielle Suche
Laufzeit Exponentielle Suche
O(log k)
Laufzeit Exponentielle Suche
(Worst Case)
O(log N)
Was bedeutet output-sensitiv?
Laufzeit hängt vom Resultat der Suche ab
Beschreib den Trivial-Select(A, i)
Laufzeit?
o(N^2)
Beschreib den Sort-Select(A, i)
Laufzeit?
o(n log n)
Beschreib den Rand-Select
Welche Laufzeit hat der Rand-Select? (Worst Case)
Wie hoch ist die erwartete Laufzeit des Rand-Select?
Was ist der Vorteil von Sortieren durch Einfügen?
ist vorteilhaft, wenn die Eingabe nahezu sortiert ist
Welchen Vorteil hat der Mergesort?
eignet sich gut für große Datenbestände auf Sekundärspeichern
Was ist die erwartete Laufzeit des randomisierten Verfahrens des Quicksorts?
O(n log n)
Wie kann ein Quicksort in der Praxis weiter beschleunigt werden?
Indem ein rekursiver Aufruf durch eine Iteration ersetzt wird (Endrekursion)
Wie viele Vergleichsoperationen benötigt jedes Sortierverfahren im Worst Case?
Gibt es einen Algorithmus der das i-te größte Element eines Arrays in linearer Laufzeit findet?
Ja
Beschreib den Select-IDX Algorithmus
Beschreib den Select-IDX5 Algorithmus
Wie lautet die Rekurrenzgleichung des Select-Algorithmus?
Skizziere, wie man k bestimmt
