Sortieralgorithmen Flashcards
Grundkonzepte
- Vergleichsoperationen und Vertauschungen: Sortieralgorithmen basieren auf dem Vergleich von Elementen mittels einer Ordnungsrelation und dem anschließenden Vertauschen von Elementen entsprechend des Vergleichsergebnisses.
- Speicherplatznutzung: Sortieralgorithmen verwenden Felder mit n Elementen (a[0], a[1], … a[n]), wobei der Speicherplatz entweder direkt am Ort (in-place) oder mit Zusatzspeicher (nicht in-place) genutzt wird.
- Interne vs. externe Sortierung: Interne Sortierung findet vollständig im Hauptspeicher statt, während externe Sortierung für Datenmengen verwendet wird, die nicht komplett in den Hauptspeicher passen und externe Speichermedien einbeziehen.
- Indexierung: Sortieralgorithmen nutzen Indizes, um auf die zu sortierenden Elemente zuzugreifen und ihre Position im Feld zu bestimmen.
- Stabilität: Ein Sortieralgorithmus ist stabil, wenn Elemente mit gleichem Schlüssel ihre relative Reihenfolge beibehalten.
- Einfluss der Vorsortierung: Die Leistung vieler Sortieralgorithmen hängt vom Grad der Vorsortierung der Eingabedaten ab. Manche Algorithmen arbeiten effizienter mit teilweise sortierten Daten.
- Zeitkomplexität: Sortieralgorithmen werden nach ihrer Effizienz in Bezug auf die Anzahl der benötigten Vergleiche und Vertauschungen klassifiziert (z.B. O(n²), O(n log n)).
Stabilität
Stabilität ist eine Eigenschaft von Sortieralgorithmen, bei der die relative Reihenfolge gleicher Elemente erhalten bleibt.
- Definition: Stabil = ursprüngliche Reihenfolge gleicher Elemente bleibt erhalten
- Anwendung: Wichtig beim mehrstufigen Sortieren (z.B. erst nach Name, dann nach Alter)
- Beispiel: Bei Personendaten bleiben bei stabilem Sortieren nach Alter die alphabetisch sortierten Namen erhalten
- Stabile Algorithmen: Insertion Sort, Merge Sort, Bubble Sort
- Nicht-stabile Algorithmen: Quick Sort, Heap Sort
Zeitkomplexität
Sortieralgorithmen werden nach ihrer Zeitkomplexität in verschiedene Klassen eingeteilt:
O(n²): Einfache Standardverfahren
- Beispiele: Insertion Sort, Bubble Sort, Selection Sort
- Einfach zu implementieren, aber ineffizient für große Datenmengen
O(n log n): Verbesserte Standardverfahren
- Beispiele: Quicksort, Mergesort, Heapsort
- Effizienteste allgemeine vergleichsbasierte Sortierverfahren
- Theoretisch optimale untere Schranke für vergleichsbasierte Algorithmen
O(n): Nicht vergleichsbasierte Verfahren
- Beispiele: Counting Sort, Radix Sort, Bucket Sort
- Setzen bestimmte Eigenschaften der Eingabedaten voraus
- Können unter speziellen Bedingungen schneller als O(n log n) sein
Selection Sort
Selection Sort ist ein einfacher Sortieralgorithmus, der durch wiederholtes Finden des kleinsten Elements arbeitet.
Funktionsweise:
- Suche das kleinste Element im unsortierten Teil
- Vertausche es mit dem ersten Element des unsortierten Teils
- Verkleinere den unsortierten Bereich und wiederhole
Komplexität:
- Vergleiche: O(n²/2) → immer quadratisch
- Vertauschungen: O(n) → linear, vorteilhaft wenn Vertauschen aufwendig ist
Eigenschaften:
- In-place (sortiert am Ort, benötigt keinen zusätzlichen Speicher)
- Stabil (in der Standardimplementierung)
- Relativ unempfindlich gegenüber der Anordnung der Eingabedaten
- Einfach zu implementieren, aber ineffizient für große Datenmengen
Insertion Sort
Insertion Sort ist ein einfacher Sortieralgorithmus, der eine Datenreihe schrittweise aufbaut.
Funktionsweise:
- Beginnt mit einem sortierten Teilbereich (anfangs nur das erste Element)
- Nimmt nacheinander jedes unsortierte Element und fügt es an der richtigen Position im sortierten Bereich ein
- Zum Einfügen werden größere Elemente nach rechts verschoben, um Platz zu schaffen
Komplexität:
- Vergleiche: O(n²/4) im Durchschnitt
- Vertauschungen: O(n²/8) im Durchschnitt
- Nahezu linear für bereits vorsortierte Daten
Eigenschaften:
- In-place (sortiert direkt im gegebenen Feld)
- Stabil (gleiche Elemente behalten ihre Reihenfolge)
- Adaptiv (profitiert von Vorsortierung)
- Einfach zu implementieren
- Effizient für kleine Datenmengen
Bubble Sort
Bubble Sort ist ein einfacher Sortieralgorithmus, der durch wiederholtes Vergleichen und Vertauschen benachbarter Elemente arbeitet.
Funktionsweise:
- Durchläuft das Array von Anfang bis Ende
- Vergleicht jeweils zwei benachbarte Elemente
- Vertauscht diese, falls sie in falscher Reihenfolge sind
- Nach jedem Durchlauf steht das größte Element am Ende
- Wiederhole für das verkürzte Array bis alles sortiert ist
Komplexität:
- Vergleiche: O(n²/2) im Durchschnitt
- Vertauschungen: O(n²/2) im Durchschnitt
- In allen Fällen quadratisch, außer bei Optimierung
Eigenschaften:
- In-place (sortiert direkt im gegebenen Feld)
- Stabil (gleiche Elemente behalten ihre Reihenfolge)
- Sehr ineffizient für große Datenmengen
- Leicht zu verstehen und zu implementieren
- Optimierung möglich: Abbruch, wenn ein Durchlauf ohne Vertauschung erfolgt
Merge Sort
Mergesort ist ein effizienter Sortieralgorithmus, der nach dem Teile-und-Herrsche-Prinzip arbeitet und von John von Neumann entwickelt wurde.
Funktionsweise:
- Teile das Feld rekursiv in zwei gleich große Hälften
- Sortiere beide Hälften rekursiv mit Mergesort
- Kopiere die sortierten Hälften in Zusatzspeicher (obere Hälfte wird dabei gespiegelt)
- Verschmelze (merge) die beiden sortierten Teilfolgen zu einer sortierten Gesamtfolge
Komplexität:
- Zeitkomplexität: O(n log n) in allen Fällen (best, average, worst)
- Platzkomplexität: O(n) für zusätzlichen Speicher
Eigenschaften:
- Stabil (erhält Reihenfolge gleicher Elemente)
- Nicht in-place (benötigt zusätzlichen Speicher)
- Gut parallelisierbar
- Effizient für große Datenmengen
- Unempfindlich gegenüber der Vorsortierung der Eingabedaten
- Häufig verwendet für externe Sortierung (wenn Daten nicht in den Hauptspeicher passen)
Quicksort
Quicksort ist ein effizienter, rekursiver Sortieralgorithmus, der auf dem Teile-und-Herrsche-Prinzip basiert und 1960 von Tony Hoare entwickelt wurde.
Funktionsweise:
- Wähle ein Pivot-Element aus dem Array
- Partitioniere das Array: Elemente kleiner als das Pivot links, größere rechts
- Wende Quicksort rekursiv auf beide Teilarrays an
- Pivot-Wahl beeinflusst die Effizienz (z.B. erstes, mittleres, zufälliges Element)
Komplexität:
- Best/Average-Case: O(n log n)
- Worst-Case: O(n²) bei ungünstiger Pivot-Wahl (z.B. bei bereits sortiertem Array)
- In-place: benötigt nur O(log n) Zusatzspeicher für Rekursionsstapel
Eigenschaften:
- Nicht stabil (ändert möglicherweise Reihenfolge gleicher Elemente)
- In-place (sortiert im ursprünglichen Array)
- Sehr effizient in der Praxis, oft schneller als andere O(n log n) Algorithmen
- Gut optimierbar (z.B. durch Medianberechnung, Insertion Sort für kleine Teilarrays)
- Anfällig für Worst-Case bei ungünstiger Datenlage (kann durch randomisierte Pivot-Wahl vermieden werden)
