MISSION 01 · 5 MINUTEN

Finde den Takt von SelectionSort.

01 / 17

Dein Auftrag

Bestimme die Laufzeit im schlechtesten Fall und in O-Notation. Starte nicht mit Formeln: Zeige zuerst auf die Arbeit, die sich oft wiederholt.

C++ → Alltag: Für jede Position i durchsucht j den gesamten noch unsortierten Rest nach dem kleinsten Wert.

for (int i = 0; i < n; ++i) {
  int minidx = i;
  for (int j = i + 1; j < n; ++j) {
    if (a[j] < a[minidx]) {
      minidx = j;
    }
  }
  swap(a, i, minidx);
}

Dein erster Zug

Welche Operation bestimmt den Takt, wenn das Array wächst?

Suche die Zeile in der inneren Schleife, die bei jedem Durchlauf geprüft wird – unabhängig von den Zahlenwerten.
swap passiert nur einmal pro äußerem i. Der Vergleich passiert dagegen für jedes verbleibende j: erst oft, dann immer seltener.

Baue die Dreieckssumme

Nimm n = 5. Klicke die äußeren Runden der Reihe nach an. Wie viele Elemente liegen jeweils noch rechts von i?

Vergleiche sichtbar: 0

Prüfungsabschluss

Vervollständige die Aussage. Schreibe eine echte Begründung, nicht nur „O(n²)“.

Noch gesperrt: erst selbst versuchen.

Wie steht Aufgabe 01?

Markiere ehrlich. Das ist Navigation für den nächsten Lernblock, keine Wertung.

Noch nicht markiert.