Sortieralgorithmen Flashcards
(8 cards)
Was sind die vier Grundbausteine von Algorithmen?
Elementare Operation:
- Basisoperationen, z.B. tausche X mit Y
Sequentielle Ausführung:
- Schritte werden nacheinander ausgeführt, z.B. Überschreiben von Variablen
Bedingte Ausführung:
- Ausführung einer Anweisung, wenn bestimmte Bedingung erfüllt ist
Schleife:
- wiederholte Ausführung einer Anweisung, so lange Bedingung erfüllt ist
Wie funktioniert die binäre Suche?
- sortierter Datensatz wird in der Hälfte geteilt
- ist der in der Mitte gelesene Wert kleiner als der gesuchte Wert, dann wird die obere Hälfte weiter geteilt
- ist der in der Mitte gelesene Wert größer als der gesuchte Wert, dann wird die untere Hälfte weiter geteilt
- Teilung so lange, bis Zielwert gefunden wird
- ist bei größeren Datensätzen deutlich effizienter als einfache sequenzielle Suche, weil nicht alle Daten abgetastet werden müssen, sondern Daten immer näherungsweise eingegrenzt werden
Was besagt die Stabilität von Sortierungen?
Ein Sortierverfahren mit bspw. zwei Spalten ist stabil, wenn die Merkmale in der ersten Spalte mehrmals auftreten und diese Datenreihen dann in der zweiten Spalte auch nach dem zweiten Kriterium sortiert werden
stabil = die Sortierung beim zweiten Merkmal bleibt erhalten
Wie funktioniert Inserion Sort?
Ausgangssituation: unsortierte Liste + eine Variable als Zwischenspeicher, um aktuellen Wert beim Verschieben von Zahlen nicht zu verlieren
1. Liste wird von vorne nach hinten abgetastet
2. abgetasteter Wert wird in Zwischenspeicher-Variable geschrieben
3. dann wird dessen Wert mit dem jeweils vorherigen Wert verglichen
4. ist der Wert davor kleiner, bleibt die Liste unverändert und man springt zum nächsten Wert
5. ist der Wert davor größer, dann wird dieser auf die aktuelle Position geschrieben (wandert also nach hinten)
6. die frei werdende Stelle davor wird dann mit dem vorigen Wert aus dem Zwischenspeicher überschrieben
7. im Zweifelsfall müssen bei sehr kleinen Werten so lange Stellen nach hinten rücken, bis der Wert ganz am Anfang steht
Wie funktioniert Merge Sort?
Ausgangssituation: unsortierte Liste
- Liste mit Werten wird schrittweise in neue Listen halbiert, bis jede Zeile eine eigene Liste darstellt
- von oben nach unten werden die Listen nun in Paaren verglichen
- der jeweils kleinere Wert wird gestrichen und nach oben in eine neue Liste geschrieben; der verbleibende (größere) Wert wird einfach darunter gesetzt
- sind alle Paare abgearbeitet, dann ist die Anzahl der Listen halbiert; wir haben nun Listen mit jeweils zwei Werten
- nun werden auch diese Listen wieder schrittweise miteinander kombiniert
- der jeweils kleinere Wert der ersten Liste wird mit dem kleineren Wert der zweiten Liste verglichen
- der kleinste Wert wird gestrichen und nach oben in eine neue Liste geschrieben
- nun werden wieder die jeweils kleinsten Werte der beiden Listen miteinander verglichen und die neue Liste entsprechend erweitert
- stellt sich eine Liste hierbei als durchgehend kleiner als die andere heraus, dann wird die andere Liste einfach unverändert (da bereits sortiert) unten dran geschrieben
- nun haben wir Listen mit jeweils vier sortierten Elementen
- diese werden wieder nach dem selben Prinzip miteinander kombiniert - Wiederholung so lange, bis die gesamte Reihe aufgelöst ist
Was sind die Vor- und Nachteile von Insertion Sort?
Stabilität: stabil
zusätzl. Speicher: nein
Aufwand: eher langsam
Was sind die Vor- und Nachteile von Merge Sort?
Stabilität: stabil
zusätzl. Speicher: ja
Aufwand: eher schnell
Was sind die Vor- und Nachteile von Quick Sort?
Stabilität: nicht stabil
zusätzl. Speicher: nein
Aufwand: eher schnell
