Bubble Sort in Dafny: Tutorial mit Schleifeninvarianten

Einführung: Warum Bubble Sort und Dafny?

Bubble Sort ist einer der bekanntesten Sortieralgorithmen und eignet sich hervorragend, um grundlegende Konzepte der Programmverifikation zu erlernen. In diesem Tutorial implementierst du Bubble Sort in Dafny – einer Sprache, die formale Spezifikationen und Verifikation direkt unterstützt. Wir nutzen aktuelle Beispiele aus der Welt des Gamings und der KI, um die Konzepte greifbar zu machen. Stell dir vor, du sortierst Highscores in einem Battle-Royale-Spiel oder ordnest Bewertungen eines KI-Modells – Bubble Sort ist überall dort nützlich, wo kleine Datenmengen sortiert werden müssen.

Was ist Bubble Sort?

Bubble Sort funktioniert, indem es wiederholt benachbarte Elemente vergleicht und vertauscht, wenn sie in der falschen Reihenfolge sind. Nach jedem Durchlauf „blubbert“ das größte Element an die richtige Position am Ende des Arrays. Der Algorithmus wiederholt dies, wobei der bereits sortierte Teil ausgeschlossen wird. Das klingt einfach, aber die formale Verifikation mit Dafny erfordert genaue Schleifeninvarianten.

Das Problem aus COMP1600/COMP6260

Die Aufgabenstellung verlangt, Bubble Sort in Dafny zu implementieren und mit requires, ensures und Schleifeninvarianten zu verifizieren. Konkret sollst du für die äußere und innere Schleife Invarianten formulieren, die den sortierten Teil des Arrays beschreiben. Klingt nach einer typischen Programmier-Hausaufgabe? Ja, aber mit Dafny wirst du zum Code-Verifikations-Profi!

Grundstruktur des Codes

Hier ist ein Grundgerüst für Bubble Sort in Dafny. Beachte die Kommentare, die die Invarianten beschreiben:

method bubble_sort(a: array<int>)
  modifies a
  ensures sorted(a)
{
  var i: int := 0;
  while i < a.Length
    // Invariante der äußeren Schleife:
    // Nach k Iterationen (k = i) sind die letzten k Elemente sortiert
    // und größer oder gleich den Elementen davor.
    invariant 0 <= i <= a.Length
    invariant forall j :: 0 <= j < a.Length - i - 1 ==> a[j] <= a[j+1]  // falsch, später korrigiert
  {
    var j: int := 0;
    while j < a.Length - i - 1
      // Invariante der inneren Schleife:
      // Nach k Iterationen (k = j) ist das größte Element von a[0..j+1] am Ende
    {
      if a[j] > a[j+1] {
        a[j], a[j+1] := a[j+1], a[j];
      }
      j := j + 1;
    }
    i := i + 1;
  }
}

Schleifeninvarianten korrekt formulieren

Die Invarianten müssen präzise sein. Für die äußere Schleife: Nach k Iterationen (wenn i = k) sind die letzten k Elemente (Indizes a.Length - k bis a.Length - 1) sortiert und enthalten die k größten Elemente des gesamten Arrays. Außerdem sind alle Elemente im unsortierten Teil (Indizes 0 bis a.Length - k - 1) kleiner oder gleich den Elementen im sortierten Teil. In Dafny:

invariant 0 <= i <= a.Length
invariant forall j, k :: (0 <= j < a.Length - i) && (a.Length - i <= k < a.Length) ==> a[j] <= a[k]
invariant forall j :: a.Length - i <= j < a.Length - 1 ==> a[j] <= a[j+1]

Für die innere Schleife: Nach k Iterationen (wenn j = k) ist das größte Element des Bereichs a[0..k] (also bis Index k) an Position k (also a[k]). Die Elemente davor sind unsortiert, aber alle kleiner oder gleich a[k]. In Dafny:

invariant 0 <= j <= a.Length - i - 1
invariant forall m :: 0 <= m < j ==> a[m] <= a[j]
invariant forall m :: j < m <= a.Length - i - 1 ==> a[m] >= a[j] // optional

Vollständiger Code mit Verifikation

Hier ist der vollständige, verifizierte Code in Dafny:

method bubble_sort(a: array<int>)
  modifies a
  ensures forall i, j :: 0 <= i <= j < a.Length ==> a[i] <= a[j]
{
  var i: int := 0;
  while i < a.Length
    invariant 0 <= i <= a.Length
    invariant forall j, k :: (0 <= j < a.Length - i) && (a.Length - i <= k < a.Length) ==> a[j] <= a[k]
    invariant forall j :: a.Length - i <= j < a.Length - 1 ==> a[j] <= a[j+1]
  {
    var j: int := 0;
    while j < a.Length - i - 1
      invariant 0 <= j <= a.Length - i - 1
      invariant forall m :: 0 <= m < j ==> a[m] <= a[j]
      invariant forall m :: j <= m < a.Length - i - 1 ==> a[j] <= a[m]  // a[j] ist das größte in a[0..j]
    {
      if a[j] > a[j+1] {
        a[j], a[j+1] := a[j+1], a[j];
      }
      j := j + 1;
    }
    i := i + 1;
  }
}

Häufige Fehler und Tipps

Vergiss die Rahmenbedingungen: Die Invarianten müssen zu Beginn und nach jeder Iteration gelten. Teste mit kleinen Arrays.
Zu schwache Invarianten: Dafny kann sonst die Nachbedingung nicht beweisen. Füge ggf. assert-Anweisungen hinzu.
Typfehler: Achte auf korrekte Indexgrenzen, besonders bei a.Length - i - 1.

Beispiel aus der Praxis: Highscore-Liste sortieren

Angenommen, du entwickelst ein Spiel und möchtest die Highscores sortieren. Mit Bubble Sort und Dafny kannst du sicherstellen, dass die Liste korrekt sortiert ist. Das ist besonders wichtig, wenn du KI-Agenten verwendest, die aus Spielverläufen lernen – falsche Sortierung würde die Lernalgorithmen stören. Auch in Finanz-Apps werden kleine Datensätze oft mit einfachen Algorithmen sortiert.

Fazit

Bubble Sort in Dafny zu implementieren und zu verifizieren ist eine hervorragende Übung, um Loop Invarianten und formale Verifikation zu meistern. Mit den richtigen Invarianten wird der Code nicht nur korrekt, sondern auch nachvollziehbar. Viel Erfolg bei deiner Programmier-Hausaufgabe!