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
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?
Wie und für welche Zahlen funktioniert der Counting Sort?
Wie funktioniert Heap-Increase-Key?
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?
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 Counting Sort?
Beschreibe den Radix Sort
Beschreibe den Bucketsort
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)
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?
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
