MINT lernen

Abituraufgaben: Selectionsort

Zwei Aufgaben auf Abiturniveau: Selectionsort durchspielen, zählen, abwandeln und auf Stabilität prüfen.

Dein Fortschritt:
0 / 0 Aufgaben
1

Pakete nach Gewicht ordnen

AFB I–II

Eine Paketstation soll eingelieferte Pakete nach ihrem Gewicht ordnen, damit schwere Pakete unten im Regal landen. Die Gewichte (in g) stehen in der Reihung gewicht. Sortiert wird aufsteigend mit Selectionsort.

Reihung gewicht vor dem Sortieren
gewicht8200350112402505329047605
  1. Beschreiben Sie das Vorgehen von Selectionsort in eigenen Worten.
  2. Stellen Sie den Ablauf für die Reihung gewicht in einer Tracetabelle dar: Nummer der Runde, i, minPos und Inhalt der Reihung nach der Runde.
  3. Geben Sie für diesen Ablauf die Anzahl der Vergleiche von Reihungselementen und die Anzahl der Runden an, in denen zwei Elemente tatsächlich ihre Plätze tauschen.
  4. Der Betreiber hofft, dass die Station schneller sortiert, wenn die Pakete schon grob nach Gewicht eingeliefert werden. Begründen Sie, dass Selectionsort dadurch keinen einzigen Vergleich einspart.

Hinweise

Hinweis zu Aufgabe a)
Zwei Teile der Reihung unterscheiden; was passiert in einer Runde?
Hinweis zu Aufgabe b)
Pro Runde eine Zeile; das Minimum wird nur im unsortierten Teil ab Index i gesucht.
Hinweis zu Aufgabe c)
Runde 1 vergleicht mit allen übrigen Elementen; zählen Sie nur Runden mit minPos ≠ i als echte Vertauschung.
Hinweis zu Aufgabe d)
Wovon hängen die Grenzen der beiden Zählschleifen ab?

Erwartungshorizont

Erwartungshorizont zu Aufgabe a)

Die Reihung besteht aus einem sortierten Teil (links, anfangs leer) und einem unsortierten Teil. In jeder Runde wird im unsortierten Teil das kleinste Element gesucht (Position merken) und mit dem ersten Element des unsortierten Teils vertauscht. Damit wächst der sortierte Teil um ein Element. Nach \(n-1\) Runden steht auch das letzte Element richtig.

Erwartungshorizont zu Aufgabe b)
RundeiminPosgewicht danach
104290 | 350 1240 505 820 760
211290 350 | 1240 505 820 760
323290 350 505 | 1240 820 760
435290 350 505 760 | 820 1240
544290 350 505 760 820 1240

Runde 2 und 5: Das Minimum steht bereits an Position i.

Erwartungshorizont zu Aufgabe c)

Vergleiche: \(5+4+3+2+1=15=\frac{6\cdot5}{2}\). Echte Vertauschungen: 3 (Runden 1, 3, 4); der Code führt den Tausch zwar 5-mal aus, in Runde 2 und 5 aber mit dem Element selbst.

Erwartungshorizont zu Aufgabe d)

Die äußere Schleife läuft immer von 0 bis \(n-2\), die innere immer von \(i+1\) bis \(n-1\). Keine der Grenzen hängt von den Werten ab, und es gibt keinen vorzeitigen Abbruch. Auch wenn das Minimum schon vorn steht, muss es mit allen restlichen Elementen verglichen werden, um sicher zu sein. Also stets \(\frac{n(n-1)}{2}\) Vergleiche; nur die Zahl der echten Vertauschungen kann sinken.

2

Eine Rangliste mit maxSort

AFB II–III

Ein Sportverein verwaltet die Punktzahlen seiner Bogenschützen in einer Reihung, zum Beispiel punkte = {58, 71, 64, 90, 33, 45}. Eine Vereinssoftware verwendet das folgende Verfahren:

  1. Analysieren Sie das Verfahren maxSort hinsichtlich der Wirkung einer Runde; notieren Sie dazu die Reihung punkte nach den ersten beiden Runden.
  2. Implementieren Sie maxSort als Java-Methode public static void maxSort(int[] a).
  3. Die Software braucht für 5000 Einträge 0,2 s. Schätzen Sie ab, wie lange sie für 10 000 Einträge braucht, wenn die Laufzeit proportional zur Anzahl der Vergleiche ist.
  4. Bei gleicher Punktzahl soll der Schütze vorn bleiben, der zuerst eingetragen wurde. Ein Mitglied schlägt vor, in der Bedingung > durch >= zu ersetzen. Erörtern Sie, ob maxSort mit oder ohne diese Änderung die Reihenfolge gleicher Punktzahlen erhält.

Hinweise

Hinweis zu Aufgabe a)
Vergleichen Sie mit Selectionsort: Welches Element wird gesucht, wohin wird es gebracht, in welcher Richtung wächst der sortierte Teil?
Hinweis zu Aufgabe b)
Äußere Schleife abwärts: for (int ende = a.length - 1; ende > 0; ende--).
Hinweis zu Aufgabe c)
Zählen Sie die Vergleiche für \(n=5000\) und \(n=10\,000\) und bilden Sie den Quotienten.
Hinweis zu Aufgabe d)
Probieren Sie kleine Beispiele mit zwei gleichen Werten, z. B. (A, 7) (B, 7) (C, 3) und (A, 5) (B, 3) (C, 3), jeweils mit > und >=.

Erwartungshorizont

Erwartungshorizont zu Aufgabe a)

In jeder Runde wird im unsortierten Bereich a[0] bis a[ende] die Position des größten Elements bestimmt und dieses mit a[ende] getauscht. Der sortierte Teil wächst damit von rechts; es entsteht ebenfalls eine aufsteigende Sortierung (Selectionsort mit Maximum).

RundeendemaxPospunkte danach
15358 71 64 45 33 | 90
24158 33 64 45 | 71 90
Erwartungshorizont zu Aufgabe b)
public static void maxSort(int[] a) {
    for (int ende = a.length - 1; ende > 0; ende--) {
        int maxPos = 0;
        for (int j = 1; j <= ende; j++) {
            if (a[j] > a[maxPos]) {
                maxPos = j;
            }
        }
        int hilf = a[ende];
        a[ende] = a[maxPos];
        a[maxPos] = hilf;
    }
}

Bewertet werden: richtige Schleifengrenzen (insbesondere j <= ende), Position statt Wert merken, Tausch mit Hilfsvariable.

Erwartungshorizont zu Aufgabe c)

Vergleiche \(V(n)=\frac{n(n-1)}{2}\): \(V(5000)=12\,497\,500\), \(V(10\,000)=49\,995\,000\). Quotient \(\approx4{,}0\). Erwartete Laufzeit \(\approx4\cdot0{,}2\,\text{s}=0{,}8\,\text{s}\). Doppelte Datenmenge bedeutet etwa vierfache Laufzeit.

Erwartungshorizont zu Aufgabe d)

Mit > wird bei Gleichstand das erste Maximum nach hinten getauscht: (A,7)(B,7)(C,3) → (C,3)(B,7)(A,7) — A stand vorn, steht nun hinter B. Mit >= wird das letzte Maximum gewählt; das hilft in manchen Fällen, aber nicht allgemein: (A,5)(B,3)(C,3) → Runde 1 tauscht A mit C: (C,3)(B,3)(A,5), Runde 2 wählt B (letztes Maximum) und lässt es stehen — C steht jetzt vor B. Ursache ist der Tausch über große Entfernungen, der unbeteiligte Elemente an gleichen Werten vorbeibewegt. Fazit: Das Verfahren ist in keiner der beiden Varianten stabil; für die Vereinsanforderung ist ein stabiles Verfahren wie Insertionsort zu wählen.