Sortieralgorithmen erforschen

1. Worum es geht

Deine Klasse hat ein gemeinsames Repository, in dem alle eure Algorithmen liegen. Was du veröffentlichst, erscheint ohne Neustart bei allen anderen und muss sich dort im Rennen und in der Messung bewähren.

Dein Algorithmus ist ganz gewöhnlicher Code: Es gibt keine Befehle zum Zeichnen und keine Hilfsfunktionen, die du aufrufen musst, damit etwas sichtbar wird. Ein vollständiger Insertion Sort in Dart sieht so aus:

import 'package:sorting_sandbox_api/sorting_sandbox_api.dart';

class InsertionSort extends SortingAlgorithm {
  String get name => 'Insertion Sort';
  String get color => Colors.purple;

  void sort(Elements list, Elements scratch) {
    for (int i = 1; i < list.length; i++) {
      final current = list[i];
      int j = i;
      while (j > 0 && list[j - 1] > current) {
        list[j] = list[j - 1];
        j--;
      }
      list[j] = current;
    }
  }
}

Eine Besonderheit: Die Zahlen selbst sieht dein Algorithmus nicht. Elemente lassen sich nur vergleichen, lesen, schreiben und vertauschen. Jeder Algorithmus in der Sandbox sortiert also nur durch Vergleichen. Für Verfahren wie Merge Sort steht eine zweite, gleich lange Liste scratch als Zwischenspeicher bereit.

Du arbeitest mit zwei Git-Repositories. Im Workspace ist ~ dein Ordner /workspace.

Die Karten auf dieser Seite schauen in deinem Workspace nach und sagen dir, was sie finden. Sie ändern nichts.

2. Einrichten

Einmalig: Zugang zu GitLab

ls ~/.ssh/id_ed25519.pub

ssh-keygen -t ed25519 -C "Vorname Nachname"

cat ~/.ssh/id_ed25519.pub

ssh -T git@git.nhcham.org

git config --global user.name "Vorname Nachname"
git config --global user.email "deine.mail@example.org"

Einmalig: Klonen

Klone die App in dein Home-Verzeichnis:

cd ~

git clone https://github.com/specht/sorting-sandbox.git

Wechsle in ihren Ordner und klone dort das Klassen-Repository:

cd sorting-sandbox

git clone git@git.nhcham.org:specht/sorting-sandbox-algorithms-2026.git algorithms

Das Klassen-Repository muss in der App liegen und genau algorithms heißen. Gibt es algorithms/ schon, klone es nicht noch einmal, sondern hol mit git pull darin den aktuellen Stand.

3. Arbeiten

Die App starten

Starte die App in einem Terminal und lass es offen. Für Git öffnest du ein zweites Terminal.

cd ~/sorting-sandbox
./run

Hol im zweiten Terminal zuerst den Stand der Klasse und lege dann im Ordner der App deinen Algorithmus an. Ersetze DEIN_NAME durch deinen Ordnernamen:

cd ~/sorting-sandbox/algorithms
git pull
cd ~/sorting-sandbox
./new-algorithm DEIN_NAME --lang python

Das legt algorithms/DEIN_NAME/bubble_sort.py mit einem Bubble Sort als Ausgangspunkt an, mit Absicht noch nicht optimiert. Statt python geht auch dart, javascript oder java. Vorhandene Dateien werden nie überschrieben.

Explore: deinem Code beim Arbeiten zusehen

Im Reiter Explore steht links dein Quelltext; du kannst ihn direkt im Browser bearbeiten, formatieren und speichern. Rechts läuft der Algorithmus Schritt für Schritt: Die aktuelle Zeile ist markiert, darunter stehen die lokalen Variablen, und Indexvariablen wie i und j erscheinen als Zeiger unter der Liste. Auf Wunsch leuchten gelesene Elemente orange und geschriebene rot auf. Mit der Zeitleiste spulst du jederzeit zurück.

Fehler sind kein Drama, du siehst sie nur deutlich: Ein Übersetzungsfehler erscheint mit Zeilennummer unter dem Editor, ein Laufzeitfehler (etwa ein Index außerhalb der Liste) in der Konsole, und eine Endlosschleife wird nach wenigen Sekunden gestoppt. Ausgaben mit print(...) landen ebenfalls in der Konsole.

Race: gleicher Auftrag, ungleiche Arbeit

Im Reiter Race treten zwei bis vier Algorithmen mit genau derselben Eingabe gegeneinander an. Jede Bahn macht pro Takt gleich viele Schritte; wer zuerst fertig ist, gewinnt. Als Eingabe gibt es zufällige, sortierte, umgekehrt sortierte und fast sortierte Listen sowie Listen mit wenigen verschiedenen Werten.

Das Rennen zeigt Arbeitsschritte, keine Laufzeit auf echter Hardware. Unter jeder Bahn stehen deshalb auch die gezählten Lese-, Schreib- und Vergleichsoperationen. Schritte, Lesen, Schreiben und Vergleichen können zu unterschiedlichen Ranglisten führen. Was heißt dann eigentlich »schneller«?

Analyze: vom Gefühl zur Wachstumsfunktion

Analyze lässt alle Algorithmen der Klasse auf Listen mit 32 bis 2048 Elementen laufen, alle mit denselben Eingaben, und zeichnet den Aufwand als Kurve. Gezählt werden Lesen, Schreiben und Vergleichen; ihre Summe heißt in der App Sandbox-Score. Die Kurven lassen sich durch n, n log n oder n² teilen und logarithmisch skalieren. Nebenbei prüft Analyze jeden Algorithmus auf Korrektheit und Stabilität.

Check: richtig, stabil oder nur zufällig richtig?

Check testet einen Algorithmus auf vielen Eingaben und zeigt bei einem Fehler die Liste, an der er scheitert. Außerdem prüft er die Stabilität: Behalten gleiche Werte ihre ursprüngliche Reihenfolge? Die Sandbox merkt sich im Hintergrund, woher jedes Element kommt; dein Code braucht dafür keine zusätzliche Zeile.

Hier hat jemand einen Selection Sort in Python geschrieben. Er sortiert richtig, ist aber nicht stabil:

from sorting_sandbox import Colors, Elements, SortingAlgorithm

class SelectionSort(SortingAlgorithm):
    name = "Selection Sort"
    color = Colors.ORANGE

    def sort(self, elements: Elements, scratch: Elements) -> None:
        n = len(elements)
        for i in range(n - 1):
            smallest = i
            for j in range(i + 1, n):
                if elements[j] < elements[smallest]:
                    smallest = j
            elements.swap(i, smallest)

Mehr zur App steht in ihrer Anleitung.

4. Veröffentlichen

Deine Klasse und deine Lehrkraft sehen deinen Algorithmus erst, wenn er committet und gepusht ist. Das machst du im Ordner algorithms, nicht im Ordner der App:

cd ~/sorting-sandbox/algorithms
git pull
git add DEIN_NAME/
git commit -m "Bubble Sort von DEIN_NAME"
git push

Nach dem Push bekommen alle anderen deinen Algorithmus mit git pull; er erscheint ohne Neustart in ihrer App. Mehrere Varianten (rekursiv und iterativ, in zwei Sprachen …) legst du einfach als weitere Dateien in deinem Ordner an; ein fehlerhafter Algorithmus stört die anderen nicht.

git pull
git push

5. Beim nächsten Mal

cd ~/sorting-sandbox && git pull
cd algorithms && git pull
cd .. && ./run

Und am Ende der Stunde: Aufgabe 5 noch einmal prüfen.