Informatik Algorithmen – Sortierverfahren im Vergleich
Karteikarten zum Thema „Informatik“ · 15 Karten · von atrio. Beispiele: Was versteht man unter der Laufzeitkomplexität eines Sortierverfahrens? · Was bedeute…
Karten
15 KartenWas versteht man unter der Laufzeitkomplexität eines Sortierverfahrens?
Rückseite
Die Laufzeitkomplexität beschreibt, wie sich die Anzahl der Operationen bei wachsender Eingabegröße n verhält, ausgedrückt in O-Notation für Best-, Average- und Worst-Case.
Was bedeutet „stabil“ bei Sortieralgorithmen?
Rückseite
Ein Sortieralgorithmus ist stabil, wenn gleichwertige Elemente ihre relative Reihenfolge nach dem Sortieren beibehalten – wichtig bei Mehrschlüsselsortierungen.
Wie lautet die Worst-Case-Laufzeit von Bubble Sort?
Rückseite
Bubble Sort hat im Worst Case O(n²) Vergleiche und Vertauschungen, da jedes Element potentielldurch das gesamte Array wandern muss.
Wie lautet die Average-Case-Laufzeit von Quicksort?
Rückseite
Quicksort erreicht im Average Case O(n log n), da das Pivot-Element die Daten durchschnittlich in zwei gleich große Partitionen teilt.
Welches Sortierverfahren hat im Best Case O(n)?
Rückseite
Insertion Sort erreicht bei bereits sortierten Daten O(n), da nur ein Vergleich pro Element nötig ist und keine Vertauschungen erfolgen.
Was ist der Unterschied zwischen internem und externem Sortieren?
Rückseite
Internes Sortieren arbeitet vollständig im Hauptspeicher, externes Sortiert nutzt Festplatten für Datensätze, die den RAM übersteigen – relevant bei großen Datenmengen.
Warum ist Merge Sort stabil, Quicksort aber nicht?
Rückseite
Merge Sort verbindet Teilarrays durch geordnetes Zusammenführen ohne Reihenfolgeänderung gleicher Elemente; Quicksort tauscht Elemente über Pivot-Grenzen hinweg und bricht Stabilität.
Wann eignet sich Insertion Sort besser als Quicksort?
Rückseite
Bei kleinen Arrays (n < 50) oder fast sortierten Daten ist Insertion Sort durch geringe Overhead-Kosten und O(n) Best Case oft schneller als Quicksort.
Was ist die Speicherplatzkomplexität von Merge Sort?
Rückseite
Merge Sort benötigt O(n) zusätzlichen Speicher für das temporäre Zusammenführen der Teilarrays – ein Nachteil gegenüber In-Place-Verfahren wie Heapsort.
Wie funktioniert das Partitionieren bei Quicksort?
Rückseite
Ein Pivot-Element wird gewählt; alle kleineren Elemente wandern links, alle größeren rechts davon – das Pivot landet an seiner finalen sortierten Position.
Welches Sortierverfahren nutzt einen Heap als Datenstruktur?
Rückseite
Heapsort baut einen binären Max-Heap auf, entnimmt wiederholt das Maximum und stellt die Heap-Eigenschaft wieder her – O(n log n) garantiert, in-place, aber instabil.
Was ist der Unterschied zwischen Counting Sort und vergleichsbasierten Verfahren?
Rückseite
Counting Sort sortiert ohne Vergleiche durch Zählen der Schlüsselwerte in O(n + k), benötigt aber ganzzahlige Schlüssel mit kleinem Wertebereich k.
Warum hat Quicksort im Worst Case O(n²)?
Rückseite
Bei ungünstiger Pivot-Wahl (z. B. immer kleinstes Element) degeneriert die Partitionierung zu n Stufen mit jeweils n Vergleichen – wie bei bereits sortierten Daten ohne Randomisierung.
Welches Verfahren wählt man für fast sortierte Daten?
Rückseite
Insertion Sort oder Timsort (Python/Java Standard) nutzen bestehende Ordnung optimal aus und erreichen nahezu O(n) bei geringen Abweichungen.
Was bedeutet „in-place“ beim Sortieren?
Rückseite
Ein In-Place-Algorithmus benötigt nur O(1) zusätzlichen Speicherplatz über die Eingabedaten hinaus – Beispiele: Quicksort, Heapsort, Insertion Sort.