Übung AFB III

Musterlösung: Gesucht wird der Wert 2, das erste Element. Die lineare Suche findet ihn nach genau einem Vergleich. Die binäre Suche beginnt in der Mitte: mitte = 15, 7, 3, 1, 0 — erst im fünften Schritt ist gerade[0] = 2 erreicht.

In diesem Fall ist die lineare Suche also schneller; die Behauptung ist widerlegt. Richtig ist: Im ungünstigsten Fall (und im Mittel bei großen \(n\)) braucht die binäre Suche viel weniger Schritte (\(\lfloor\log_2 n\rfloor+1\) statt \(n\)).

Musterlösung:

Ablauf: max/zweit = 14/−∞ → 27/14 → 27/14 (9) → 27/14 (27 gleich max, ignoriert) → 27/21 → 27/21 (18). Ergebnis 21. Ohne die Bedingung punkte[i] < max würde die zweite 27 als „zweitgrößter“ Wert gespeichert. Der Algorithmus braucht höchstens \(2(n-1)\) Vergleiche — linear, statt quadratisch wie Sortieren mit Selectionsort.

Musterlösung:

public static boolean istSortiert(int[] a) {
    for (int i = 1; i < a.length; i++) {
        if (a[i] < a[i - 1]) {
            return false;   // erstes falsches Paar
        }
    }
    return true;            // kein falsches Paar gefunden
}

Für die Reihung werden (2,5), (5,5), (5,9) und (9,4) geprüft: 4 Vergleiche, Ergebnis false. Bei einer sortierten Reihung der Länge \(n\) sind es \(n-1\) Vergleiche. Wichtig: return true steht nach der Schleife; ein else return true in der Schleife würde schon nach dem ersten Paar antworten. Die Bedingung < (nicht <=) lässt gleiche Nachbarn zu.

Musterlösung: Selectionsort: D1 vertauscht Jana ↔ Ben → Ben 7 · Emil 9 · Lotta 12 · Jana 12. Die weiteren Durchläufe ändern nichts. Jana steht an Index 3, also hinter Lotta, obwohl sie vorher vor ihr stand. Das weite Vertauschen über andere Elemente hinweg macht Selectionsort instabil.

Insertionsort verschiebt nur, solange das linke Element echt größer ist, und überholt gleich große Elemente nie: Ergebnis Ben · Emil · Jana · Lotta. Insertionsort (ebenso Bubblesort mit >) ist stabil und erfüllt die Anforderung; Selectionsort ist ungeeignet.

Musterlösung: Variante A: \(1000\) Vergleiche pro Suche, also \(1000k\). Variante B: Sortieren \(\frac{1000\cdot999}{2} = 499\,500\), dann je Suche \(\lfloor\log_2 1000\rfloor + 1 = 10\): \(499\,500 + 10k\).

\(499\,500 + 10k < 1000k \iff 990k > 499\,500 \iff k > 504{,}5\). Ab 505 Suchanfragen ist B günstiger (504 550 gegen 505 000 Vergleiche).

Abwägung: Bei wenigen Anfragen oder häufig wechselnden Daten ist A besser, weil nach jeder Änderung neu sortiert werden müsste. Bei vielen Anfragen auf festen Daten gewinnt B deutlich. Mit einem schnelleren Sortierverfahren als Selectionsort läge die Grenze viel niedriger.

Musterlösung: Die äußere Schleife läuft nur bis i < 3 statt bis i < n − 1:

for (int i = 0; i < 3; i++) {          // statt i < zeit.length - 1
    int min = i;
    for (int j = i + 1; j < zeit.length; j++) {
        if (zeit[j] < zeit[min]) {
            min = j;
        }
    }
    int h = zeit[i]; zeit[i] = zeit[min]; zeit[min] = h;
}

Vergleiche: \(9 + 8 + 7 = 24\) statt \(\frac{10\cdot9}{2} = 45\). Allgemein für die \(k\) kleinsten Werte: \((n-1) + (n-2) + \dots + (n-k)\), bei festem \(k\) also nur linear in \(n\). Insertionsort oder Bubblesort (Größte nach hinten) eignen sich dafür nicht so direkt.

Musterlösung: 5, 12 und 17 werden gefunden. Bei 8 und 23 schrumpft der Suchbereich auf ein Element (links = rechts = 1 bzw. = 4); die Bedingung links < rechts ist dann falsch, und die Methode gibt −1 zurück, obwohl der Wert genau dort steht. Also werden 2 Werte nicht gefunden.

Korrektur: while (links <= rechts) — ein Bereich aus einem einzigen Element muss noch geprüft werden. Solche Fehler findet man mit Tests am Rand (erstes, letztes Element) und bei Bereichen der Länge 1.

Musterlösung: Im Durchlauf mit Index \(i\) (von 0 bis \(n-2\)) wird das aktuelle Minimum mit allen \(n-1-i\) Elementen rechts davon verglichen. Das ergibt \(S=(n-1)+(n-2)+\dots+1\). Schreibt man die Summe zusätzlich rückwärts darunter und addiert, entsteht \(n-1\)-mal der Wert \(n\): \(2S=n(n-1)\), also \(S=\frac{n(n-1)}{2}\).

\(n = 1414\): \(\frac{1414\cdot1413}{2}=998\,991\); \(n = 1415\): \(\frac{1415\cdot1414}{2}=1\,000\,405\). Also ab \(n = 1415\). Die Anzahl hängt nicht von der Vorsortierung ab, weil jede Minimumsuche den ganzen Rest ansieht.

Musterlösung: \(365\cdot24\cdot8 = 70\,080\) Byte (≈ 68 KiB). Eine Kopie des ganzen Jahres pro Tag würde denselben Speicher noch einmal belegen, bei 365 Kopien gleichzeitig sogar etwa 25 MB — ohne jeden Nutzen.

Bewertung: Der Vorschlag ist ungünstig. Die drei behandelten Sortierverfahren arbeiten in der Reihung selbst und brauchen nur eine Hilfsvariable zum Tauschen. Soll die Originalreihenfolge erhalten bleiben, genügt eine Kopie eines Tages (feuchte[t], 24 Werte, 192 Byte). Sinnvoll: Speicher sparen, wenn die Daten es erlauben.

Musterlösung: Selectionsort braucht immer \(\frac{10\cdot9}{2}=45\) Vergleiche. Bubblesort mit Abbruch: Durchlauf 1 (9 Vergleiche) tauscht 16 und 15, Durchlauf 2 (8 Vergleiche) bestätigt die Ordnung → 17. Insertionsort: Jedes Element außer 15 braucht einen Vergleich (8), die 15 vergleicht mit 16 (verschieben) und 14 (stopp) → 10 Vergleiche, eine Verschiebung.

Entscheidung: Insertionsort. Es nutzt vorhandene Ordnung am besten aus und kommt bei fast sortierten Daten mit etwa \(n\) Vergleichen aus.