⚖️

Sortier-Waage

Vergleiche Klötze durch Wiegen auf der Waage und ordne sie von leicht nach schwer. Entdecke dabei elementare Sortierverfahren und lerne, wie viele Vergleiche verschiedene Strategien benötigen.

Simulation Interaktiv Kursstufe Algorithmen
🎯 Worum geht's? Klasse 11 · 1 Unterrichtsstunde

Nach dieser Seite kannst du …

  • Gewichte nur durch paarweises Vergleichen sortieren
  • deine Strategie mit Sortierverfahren wie Bubble Sort und Selection Sort vergleichen
  • die Zahl der nötigen Vergleiche abschätzen

Vorwissen: keines

7
⚖️ Vergleiche 0
📊 Fortschritt 0 %
⏱️ Zeit 0:00

⚖️ Vergleichs-Waage

Ziehe einen Klotz auf die linke oder rechte Schale
Links
Rechts

🎲 Deine Sortierung — Slot 0 = leichtester

⌨️ Ohne Maus: Klotz mit Tab ansteuern, ← → tauscht mit dem Nachbarplatz, L/R legt ihn auf die linke/rechte Schale, Entf nimmt ihn herunter. Oder: Enter wählt einen Klotz, Enter auf einem anderen Klotz tauscht die beiden.

✅ Korrekte Reihenfolge

📖 Info

⚖️ Das Waagenmodell

Beim Waagenmodell ist der einzige erlaubte Vergleich das Wiegen.

📌 MerksatzJeder Vergleich kostet eine Zeiteinheit. Ziel: möglichst wenige Vergleiche.
  • Links schwerer: linke Schale sinkt
  • Rechts schwerer: rechte Schale sinkt
  • Gleich: Waage im Gleichgewicht
⚠️ BeachteMan erkennt nur wer schwerer ist, nicht um wie viel.

🔢 Elementare Sortierverfahren

1. Selection Sort – „Minimum suchen und tauschen“

Vorgehen:

  1. Suche das leichteste Element im unsortierten Bereich.
  2. Tausche es mit dem ersten unsortierten Element.
  3. Wiederhole für den Rest.
📌 MerksatzImmer genau n·(n-1)/2 Vergleiche.

Beispiel:

Klötze: [C, A, B] → [A, C, B] → [A, B, C] (sortiert).

2. Insertion Sort – „Einfügen an der richtigen Stelle“

Vorgehen:

  1. Betrachte den nächsten Klotz als „Schlüssel“.
  2. Verschiebe ihn nach links, bis er an der richtigen Stelle ist.
  3. Füge ihn ein.
📌 MerksatzIm besten Fall nur n−1 Vergleiche.

Beispiel:

Klötze: [C, A, B] → [A, C, B] → [A, B, C] (sortiert).

3. Bubble Sort – „Blasen lassen: Schweres sinkt nach unten“

Vorgehen:

  1. Vergleiche benachbarte Klötze von links nach rechts.
  2. Tausche sie, wenn sie falsch herum liegen.
  3. Wiederhole, bis keine Tauschungen mehr nötig sind.
📌 MerksatzEinfach, aber langsam – im schlimmsten Fall O(n²) Vergleiche.

Beispiel:

Klötze: [C, A, B] → [A, C, B] → [A, B, C] (sortiert).

📌 MerksatzInsertion Sort ist gut für fast sortierte Listen, Selection Sort ist vorhersehbar, Bubble Sort ist einfach – aber langsam!

📈 Laufzeitanalyse

Algorithmus Best Avg Worst Stabil
Selection O(n²) O(n²) O(n²) Nein
Insertion O(n) O(n²) O(n²) Ja
Bubble O(n) O(n²) O(n²) Ja
Merge O(n·log n) O(n·log n) O(n·log n) Ja
Quick O(n·log n) O(n·log n) O(n²) Nein
📌 Untere SchrankeKein vergleichsbasierter Algorithmus schlägt O(n·log n) im Durchschnitt.
💡 PrüfungstippO(n²) vs. O(n·log n) erklären können!
Beste Ergebnisse nach Score