Aufgaben: Sortierverfahren und Effizienz

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 [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 [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.

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;

    }

}

1. a) Benennen Sie das Verfahren.

1. b) Geben Sie die Feldzustände nach jedem Durchlauf der äußeren Schleife für a = {9, 4, 7, 3, 8} an.

1. c) Wie viele Vergleiche führt die innere Schleife insgesamt bei einem Feld der Länge 5 aus?

Ein Lehrer der Realschule in Kassel möchte Klausurpunkte [12, 7, 15, 7, 10, 3] absteigend sortieren.

1. a) Passen Sie Bubblesort so an, dass es absteigend sortiert, und beschreiben Sie die Änderung im Algorithmus.

1. b) Führen Sie das Verfahren vollständig durch.

1. 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.

Für ein Feld der Länge $n$ gilt bei Selectionsort und Bubblesort ungefähr $\frac{n(n-1)}{2}$ Vergleiche.

1. a) Berechnen Sie die Zahl der Vergleiche für $n = 10$, $n = 100$ und $n = 1.000$.

1. b) Um welchen Faktor steigt der Aufwand ungefähr, wenn $n$ verzehnfacht wird? Welche Aufwandsklasse folgt daraus?

1. 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].

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).

1. b) Welches Verfahren ist bei (A) am günstigsten? Begründen Sie.

1. c) Beurteilen Sie, welche Rolle der Speicherplatzbedarf hier spielt, wenn alle drei Verfahren „in place“ arbeiten.

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.

1. a) Beschreiben Sie das Zusammenführen (Merge) in Pseudocode.

1. 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.

1. c) Welchen zusätzlichen Speicherplatz benötigt das Zusammenführen im Vergleich zu Selectionsort?

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.

1. a) Beurteilen Sie, ob Insertionsort oder Selectionsort besser geeignet ist, und begründen Sie anhand der Zahl der Vergleiche.

1. b) Schätzen Sie den Aufwand beider Verfahren in Größenordnungen ab.

1. c) Nennen Sie ein Kriterium neben der Laufzeit, das bei der Wahl eines Verfahrens eine Rolle spielen kann.