Vergleiche und Vertauschungen

Intermediate Algorithmen und Datenstrukturen Deutsch

Also available: English

Created by Best · 16.08.2026 at 09:13 UTC

Analysiere getrennt: Vergleiche (Lesen) und Schreib-/Tauschkosten. Selection Sort: viele Vergleiche, wenige Swaps. Insertion Sort: bei Unordnung viele Verschiebungen.

Wo gebraucht

Kostenmodell wenn Vergleiche teuer sind (grosse Objekte, Remote-Keys). Erklärt, warum man Keys extrahiert oder Schwartzian-ähnlich vorverarbeitet.

Vertiefung

Kosten einer Sortierung bestehen nicht nur aus Vergleichen. Je nach Datentyp können Schreibzugriffe, Kopien oder Bewegungen deutlich teurer sein. Selection Sort prüft den unsortierten Rest vollständig, bewegt aber nur am Rundenende Elemente. Insertion Sort kann auf günstigen Eingaben mit wenigen Prüfungen und Verschiebungen auskommen.

Für Selection Sort addieren sich Restlängen wie n minus eins, n minus zwei bis eins. Die Bewegungszahl wächst wesentlich langsamer. Diese Trennung erklärt, warum ein Verfahren trotz vieler Schlüsselvergleiche bei teuren Schreibmedien interessant sein kann.

Schwierigkeitsstufen

Vergleiche und Datenbewegungen in einer Runde getrennt zählen.
Summen über schrumpfende Restbereiche aufstellen.
Ein Verfahren anhand unterschiedlicher Kostenmodelle auswählen.

Fallstricke

Ein Tausch umfasst mehrere Schreibzugriffe und ist nicht mit einem einzelnen Vergleich gleichzusetzen. Big-O allein verdeckt zudem konstante Faktoren und unterschiedliche Operationskosten.

University approvals: 0

Tasks

Question 1

Welche Aussage trifft Selection Sort?

Immer O(n log n) Vergleiche

Theta(n^2) Vergleiche, höchstens n Swaps

Keine Vergleiche

Nur für Strings

Question 2

Wann kann Selection Sort trotz vieler Schlüsselprüfungen interessant sein?

Wenn Schreiboperationen besonders teuer sind.

Wenn jeder Vergleich verboten ist.

Wenn Stabilität unabhängig von der Implementierung garantiert sein muss.

Wenn der Restbereich nie untersucht werden darf.

Question 3

Implementiere Selection Sort und gib die Zahl der Elementvergleiche und tatsächlichen Vertauschungen zurück.

Hint

Die Zählerfelder haben den Typ long. Ein Ergebnisobjekt wird mit new SelectionStats(comparisons, swaps) erzeugt.

class SelectionStats {
  final long comparisons;
  final long swaps;

  SelectionStats(long comparisons, long swaps) {
    this.comparisons = comparisons;
    this.swaps = swaps;
  }

  static SelectionStats sort(int[] a) {
    // TODO
    return null;
  }
}

Starter code is prefilled; replace TODO blocks with your solution.

Runtime output (stdout/stderr)

1 test case will be used for grading

Run checks runtime behavior only. Final correctness is evaluated when you submit.

Card Info

Topic: Algorithmen und Datenstrukturen
Difficulty: Intermediate
Completed: 0 users

Creator

Best

BestBuddy