Sortierverfahren und Effizienz
Eine Lehrkraft in Köln hat die Klausurpunkte ihres Kurses in beliebiger Reihenfolge notiert und möchte eine Rangliste erstellen. Bei 6 Werten gelingt das „mit dem Auge“. Bei 50.000 Bestellungen in einem Online-Shop nicht mehr: Ein Computer braucht eine genaue Vorschrift. Wie sieht eine solche Vorschrift aus, und wie viel Arbeit kostet sie, wenn das Feld doppelt oder zehnmal so groß wird?
Im Folgenden wird ein Feld (Array) a mit ganzen Zahlen aufsteigend sortiert. Alle drei Verfahren arbeiten „in place“: Sie vertauschen oder verschieben Werte im selben Feld und brauchen keinen zweiten großen Speicherbereich.
Selectionsort: immer das Minimum nach vorn
Die Idee kennt jeder vom Kartenspiel: Aus dem unsortierten Rest wird die kleinste Karte gesucht und nach vorn gelegt. Danach ist ein Stück am Anfang endgültig sortiert, und das Verfahren wiederholt sich mit dem Rest.
public static void selectionsort(int[] a) {
for (int i = 0; i < a.length - 1; i++) {
int min = i;
for (int j = i + 1; j < a.length; j++) {
if (a[j] < a[min]) min = j;
}
int t = a[i]; a[i] = a[min]; a[min] = t;
}
}
Die äußere Schleife wählt die Zielposition i, die innere Schleife sucht den Index min. Gesucht wird erst, vertauscht wird danach: pro Durchlauf höchstens eine Vertauschung.
Sortieren Sie das Feld [5, 2, 9, 1, 7] aufsteigend mit Selectionsort. Geben Sie nach jedem Durchlauf der äußeren Schleife den Zustand des Feldes an.
Sortieren Sie das Feld [5, 2, 9, 1, 7] aufsteigend mit Selectionsort. Geben Sie nach jedem Durchlauf der äußeren Schleife den Zustand des Feldes an.
Gegeben ist die Java-Methode: a) Benennen Sie das Verfahren. b) Geben Sie die Feldzustände nach jedem Durchlauf der äußeren Schleife für a = {9, 4, 7, 3, 8} an. c) Wie…
Gegeben ist die Java-Methode:
public static void sortiere(int[] a) {
for (int i = 0; i < a.length - 1; i++) {
int min = i;
for (int j = i + 1; j < a.length; j++) {
if (a[j] < a[min]) min = j;
}
int t = a[i]; a[i] = a[min]; a[min] = t;
}
}
- a) Benennen Sie das Verfahren.
- b) Geben Sie die Feldzustände nach jedem Durchlauf der äußeren Schleife für
a = {9, 4, 7, 3, 8}an.
- c) Wie viele Vergleiche führt die innere Schleife insgesamt bei einem Feld der Länge 5 aus?
Bubblesort: große Werte steigen auf
Beim Bubblesort werden benachbarte Elemente verglichen und bei falscher Reihenfolge vertauscht. Der größte Wert „steigt“ dabei wie eine Blase nach rechts.
public static void bubblesort(int[] a) {
for (int i = a.length - 1; i > 0; i--) {
for (int j = 0; j < i; j++) {
if (a[j] > a[j + 1]) {
int t = a[j]; a[j] = a[j + 1]; a[j + 1] = t;
}
}
}
}
Verbesserung: vorzeitiger Abbruch
Wird in einem ganzen Durchlauf nicht ein einziges Mal vertauscht, ist das Feld sortiert. Man merkt sich das in einer Variablen boolean getauscht, die vor jedem Durchlauf auf false gesetzt und bei jeder Vertauschung auf true gesetzt wird. Ist sie nach dem Durchlauf noch false, bricht die äußere Schleife ab. Bei einem schon sortierten Feld genügt dann ein Durchlauf statt $n-1$.
Für absteigendes Sortieren muss nur die Bedingung gedreht werden: if (a[j] < a[j + 1]) statt >.
Sortieren Sie das Feld [4, 3, 6, 1, 2] aufsteigend mit Bubblesort. Geben Sie das Feld nach jedem vollständigen Durchlauf an und zählen Sie die Vertauschungen.
Sortieren Sie das Feld [4, 3, 6, 1, 2] aufsteigend mit Bubblesort. Geben Sie das Feld nach jedem vollständigen Durchlauf an und zählen Sie die Vertauschungen.
Ein Lehrer der Realschule in Kassel möchte Klausurpunkte [12, 7, 15, 7, 10, 3] absteigend sortieren. a) Passen Sie Bubblesort so an, dass es absteigend sortiert, und…
Ein Lehrer der Realschule in Kassel möchte Klausurpunkte [12, 7, 15, 7, 10, 3] absteigend sortieren.
- a) Passen Sie Bubblesort so an, dass es absteigend sortiert, und beschreiben Sie die Änderung im Algorithmus.
- b) Führen Sie das Verfahren vollständig durch.
- c) Erklären Sie, wie man Bubblesort abbrechen kann, sobald in einem Durchlauf nicht mehr vertauscht wurde, und wie viele Durchläufe dies bei einem bereits sortierten Feld spart.
Insertionsort: wie Karten einsortieren
Wer Handkarten sortiert, nimmt die nächste Karte und schiebt sie in den schon sortierten Teil an die richtige Stelle. Genau das macht Insertionsort.
public static void insertionsort(int[] a) {
for (int i = 1; i < a.length; i++) {
int x = a[i];
int j = i - 1;
while (j >= 0 && a[j] > x) {
a[j + 1] = a[j];
j--;
}
a[j + 1] = x;
}
}
Sortieren Sie das Feld [6, 4, 8, 2, 5] aufsteigend mit Insertionsort. Geben Sie nach jedem Einfügeschritt den Zustand des Feldes an und markieren Sie den sortierten Teil.
Sortieren Sie das Feld [6, 4, 8, 2, 5] aufsteigend mit Insertionsort. Geben Sie nach jedem Einfügeschritt den Zustand des Feldes an und markieren Sie den sortierten Teil.
Effizienz: Zeitaufwand und Speicherbedarf
Die Laufzeit hängt vom Rechner ab. Der Zeitaufwand eines Algorithmus wird deshalb in Schritten gemessen, meist in der Zahl der Vergleiche (und der Vertauschungen), abhängig von der Länge $n$ des Feldes.
Bei Selectionsort und Bubblesort (ohne Abbruch) wird jedes Paar höchstens einmal verglichen:
$$(n-1) + (n-2) + \dots + 1 = \frac{n(n-1)}{2}$$| $n$ | Vergleiche $\frac{n(n-1)}{2}$ |
|---|---|
| 10 | 45 |
| 100 | 4.950 |
| 1.000 | 499.500 |
Verzehnfacht man $n$, steigt der Aufwand ungefähr auf das Hundertfache. Der Aufwand wächst also etwa wie $n^2$: Man spricht von quadratischem Aufwand.
Speicherplatzbedarf
Selectionsort, Bubblesort und Insertionsort brauchen außer dem Feld nur wenige Hilfsvariablen (t, min, x, Zähler). Der zusätzliche Speicher ist konstant, unabhängig von $n$. Solche Verfahren heißen in place. Verfahren, die für jede Größe $n$ ein zweites Feld der Länge $n$ anlegen, brauchen dagegen zusätzlichen Speicher, der mit $n$ wächst.
Zur Wahl eines Verfahrens zählen neben der Laufzeit auch der Speicherbedarf, die Einfachheit des Quellcodes (weniger Fehler, leichter zu überprüfen), das Verhalten bei teilweise sortierten Daten und die Frage, ob gleiche Werte ihre Reihenfolge behalten (Stabilität).
Für ein Feld der Länge $n$ gilt bei Selectionsort und Bubblesort ungefähr $\frac{n(n-1)}{2}$ Vergleiche. a) Berechnen Sie die Zahl der Vergleiche für $n = 10$, $n = 100$…
Für ein Feld der Länge $n$ gilt bei Selectionsort und Bubblesort ungefähr $\frac{n(n-1)}{2}$ Vergleiche.
- a) Berechnen Sie die Zahl der Vergleiche für $n = 10$, $n = 100$ und $n = 1.000$.
- b) Um welchen Faktor steigt der Aufwand ungefähr, wenn $n$ verzehnfacht wird? Welche Aufwandsklasse folgt daraus?
- c) Ein Rechner schafft 10 Millionen Vergleiche pro Sekunde. Wie lange braucht er für $n = 100.000$?
Vergleichen Sie Selectionsort, Bubblesort und Insertionsort anhand folgender Felder der Länge 6: (A) [1, 2, 3, 4, 5, 6], (B) [6, 5, 4, 3, 2, 1]. a) Geben Sie für jedes…
Vergleichen Sie Selectionsort, Bubblesort und Insertionsort anhand folgender Felder der Länge 6:
(A) [1, 2, 3, 4, 5, 6], (B) [6, 5, 4, 3, 2, 1].
- a) Geben Sie für jedes Verfahren und jedes Feld die Anzahl der Vergleiche und Vertauschungen bzw. Verschiebungen an (Selectionsort vertauscht in jedem Durchlauf, auch wenn das Minimum bereits an Position $i$ steht; Bubblesort ohne vorzeitigen Abbruch; Insertionsort mit Verschiebung statt Vertauschung, wobei die innere Schleife endet, sobald $a[j-1] \le$ Schlüssel gilt).
- b) Welches Verfahren ist bei (A) am günstigsten? Begründen Sie.
- c) Beurteilen Sie, welche Rolle der Speicherplatzbedarf hier spielt, wenn alle drei Verfahren „in place“ arbeiten.
Ein Online-Shop in Berlin sortiert täglich 50.000 Bestellungen nach Bestellnummer. Die Bestellungen kommen größtenteils bereits sortiert an, nur wenige Einträge am Ende…
Ein Online-Shop in Berlin sortiert täglich 50.000 Bestellungen nach Bestellnummer. Die Bestellungen kommen größtenteils bereits sortiert an, nur wenige Einträge am Ende sind neu und unsortiert.
- a) Beurteilen Sie, ob Insertionsort oder Selectionsort besser geeignet ist, und begründen Sie anhand der Zahl der Vergleiche.
- b) Schätzen Sie den Aufwand beider Verfahren in Größenordnungen ab.
- c) Nennen Sie ein Kriterium neben der Laufzeit, das bei der Wahl eines Verfahrens eine Rolle spielen kann.
Einen eigenen Sortieralgorithmus entwerfen
Die drei Verfahren sind nicht die einzigen. Neue Algorithmen entstehen oft aus einer Idee, die man in Pseudocode und dann in Programmcode ausarbeitet. Hier die Idee „Teilen und Zusammenführen“:
-
Teile das Feld in zwei Hälften.
-
Sortiere jede Hälfte für sich (mit einem einfachen Verfahren).
-
Führe die beiden sortierten Hälften zu einem sortierten Feld zusammen (Merge).
Der Kern ist das Zusammenführen. Zwei Zeiger zeigen jeweils auf das vorderste noch nicht übernommene Element jeder Hälfte. Immer das kleinere wird in das Ergebnisfeld übernommen.
Eingabe: sortierte Felder L (Länge p) und R (Länge q)
i ← 0; j ← 0; k ← 0
solange i < p und j < q wiederhole
wenn L[i] ≤ R[j] dann
E[k] ← L[i]; i ← i + 1
sonst
E[k] ← R[j]; j ← j + 1
ende wenn
k ← k + 1
ende solange
kopiere die restlichen Elemente von L (ab i) bzw. R (ab j) nach E
Ausgabe: E
Entwerfen Sie einen eigenen Sortieralgorithmus nach folgender Idee: Das Feld wird in zwei Hälften geteilt, jede Hälfte wird für sich sortiert, anschließend werden beide…
Entwerfen Sie einen eigenen Sortieralgorithmus nach folgender Idee: Das Feld wird in zwei Hälften geteilt, jede Hälfte wird für sich sortiert, anschließend werden beide sortierten Hälften zu einem sortierten Feld zusammengeführt.
- a) Beschreiben Sie das Zusammenführen (Merge) in Pseudocode.
- b) Führen Sie das Verfahren für
[8, 3, 5, 1, 9, 2]aus, wobei die Hälften mit einem beliebigen einfachen Verfahren sortiert werden.
- c) Welchen zusätzlichen Speicherplatz benötigt das Zusammenführen im Vergleich zu Selectionsort?
Zurück zum Anfang: Die Lehrkraft in Köln kann ihre sechs Punktzahlen mit jedem der drei Verfahren sortieren. Bei 6 Werten sind das höchstens 15 Vergleiche. Bei 50.000 Bestellungen wären es fast 1,25 Milliarden: Dann entscheidet man mit Aufwand, Speicherbedarf und Vorsortierung, welches Verfahren sich eignet.