Sortieren

Aufgabe

So unterscheiden sich die drei Verfahren

Alle drei Algorithmen kennen Sie aus der Vorlesung und den Shorts dazu. Für die Aufgabe kommt es darauf an, wie ihre Laufzeit von der Größe $n$ und der Reihenfolge der Eingabe abhängt:

Selection Sort sucht im unsortierten Teil der Liste immer wieder das kleinste Element und setzt es an seine endgültige Stelle. Dabei durchsucht er den unsortierten Teil jedes Mal vollständig, egal wie die Liste vorher aussah.
Bubble Sort vergleicht benachbarte Werte und vertauscht sie, wenn sie in der falschen Reihenfolge stehen. Er hört auf, sobald ein Durchlauf ohne Vertauschung bleibt.
Merge Sort teilt die Liste rekursiv in zwei Hälften, sortiert beide und fügt sie in der richtigen Reihenfolge wieder zusammen.

Algorithmus	schlechtester Fall	bester Fall
Selection Sort	$O(n^2)$	$\Omega(n^2)$
Bubble Sort	$O(n^2)$	$\Omega(n)$
Merge Sort	$O(n \log n)$	$\Omega(n \log n)$

Beispiel: Was passiert, wenn die Liste zehnmal so lang wird, etwa 50000 statt 5000 Zahlen?

Laufzeit wächst wie	Rechnung	Zeit etwa
$n$	$50000 / 5000 = 10$	10-mal so lang
$n \log n$	$(50000 \cdot \log_2 50000) / (5000 \cdot \log_2 5000) \approx 10 \cdot 15.6 / 12.3$	13-mal so lang
$n^2$	$50000^2 / 5000^2 = 10^2$	100-mal so lang

Bei den kleinen Dateien liegen die Zeiten der drei Programme so nah beieinander, dass man kaum etwas erkennt. Deutlich werden die Unterschiede erst bei den großen Dateien.

Aufgabenmaterial

Sie erhalten die drei bereits kompilierten C-Programme sort1, sort2 und sort3, mehrere .txt-Dateien als Eingabe und die Datei answers.txt für Ihre Antworten.

Aufgabenmaterial herunterladen

Öffnen Sie VS Code entsprechend Ihrem Setup.

Öffnen Sie Ihr Terminalfenster und führen Sie dann cd aus. Die Eingabeaufforderung Ihres Terminalfensters sollte wie folgt aussehen:

Geben Sie dann

wget https://dev.inf.zone/download/exercises/05/sort.zip

ein und führen Sie den Befehl mit der Eingabetaste aus, um eine ZIP-Datei namens sort.zip in den aktuellen Ordner herunterzuladen. Achten Sie darauf, dass Sie das Leerzeichen zwischen wget und der folgenden URL nicht übersehen, und auch kein anderes Zeichen!

Führen Sie jetzt

unzip sort.zip

aus, um das ZIP-Archiv in einen Ordner namens sort zu extrahieren. Sie brauchen die ZIP-Datei nicht mehr, also können Sie

rm sort.zip

ausführen. Antworten Sie mit “y”, gefolgt von der Eingabetaste, um die heruntergeladene ZIP-Datei zu entfernen. Führen Sie dann

cd sort

aus, um in dieses Verzeichnis zu wechseln. Ihre Eingabeaufforderung sollte nun wie folgt aussehen:

sort/ $

Spezifikation

Die Textdateien heißen nach ihrem Inhalt: sorted, reversed oder random und die Zahl der Zeilen (5000, 10000 oder 50000). reversed10000.txt enthält zum Beispiel die Zahlen von 10000 absteigend bis 1, random50000.txt 50000 Zahlen in zufälliger Reihenfolge.
Ein Programm starten Sie mit ./[Programmname] [Textdatei], zum Beispiel ./sort1 reversed10000.txt. Es gibt die Zahlen sortiert aus.
Ersetzen Sie in answers.txt jedes TODO: hinter sort1 uses: usw. den Namen des Algorithmus (Selection Sort, Bubble Sort oder Merge Sort), hinter How do you know?: eine kurze Begründung, gestützt auf Ihre Messungen. Die übrigen Zeilen lassen Sie unverändert.

Hilfestellung

Klicken Sie auf die folgenden Tipps, um einige Ratschläge zu erhalten!

Untersuchen Sie die .txt-Dateien

Die verschiedenen Arten von Dateien helfen Ihnen, die Algorithmen auseinanderzuhalten. Überlegen Sie mit der Tabelle oben, wie jeder Algorithmus bei einer bereits sortierten Liste abschneidet, wie bei einer umgekehrten und wie bei einer gemischten. Es kann helfen, eine kleine Liste jedes Typs von Hand mit jedem Verfahren durchzugehen.

Messen Sie die Zeit für jede Sortierung mit verschiedenen Eingaben

Wechseln Sie mit cd in das Verzeichnis sort und setzen Sie time vor den Aufruf: time ./sort1 reversed10000.txt misst, wie lange sort1 für 10000 absteigend sortierte Zahlen braucht.
Am Ende der Ausgabe steht unter real die Zeit, die bei der Ausführung tatsächlich verstrichen ist.
Die sortierten Zahlen auszugeben, kostet im Terminal selbst Zeit. Mit time ./sort1 reversed10000.txt > /dev/null verwerfen Sie die Ausgabe und messen nur das Sortieren.
Vergleichen Sie für jedes Programm dieselbe Dateigröße mit verschiedener Reihenfolge und dieselbe Reihenfolge mit verschiedenen Größen.

Befehle schneller eingeben

Mit Strg+Shift+C und Strg+Shift+V (unter Windows, sonst rechter Mausklick in das Terminalfenster) kopieren Sie Text in die Kommandozeile und aus ihr heraus. Frühere Befehle holen Sie mit den Pfeiltasten (hoch/runter) oder Strg+R zurück.

Testen

Korrektheit

Führen Sie in Ihrem Terminal den folgenden Befehl aus, um die Korrektheit Ihrer Arbeit zu überprüfen:

check50 -l inf-zone/exercises/2026/sort

Abgeben

Geben Sie im Ordner sort ab:

inf upload sort

Danach sehen Sie, welche Tests Ihr Programm besteht und ob die Übung für die Bonuspunkte zählt. Wie Sie inf installieren und sich anmelden, steht unter Abgeben mit inf.

Diese Seite als Markdown: ansehen herunterladen

Mehrheitswahl