Sortieren

Aufgabe

In der Vorlesung (und in den Shorts dazu) haben wir uns einige Algorithmen zum Sortieren einer Zahlenfolge angeschaut: Selection Sort, Bubble Sort und Merge Sort.

Zur Erinnerung:

  • Selection Sort durchläuft die unsortierten Teile einer Liste, wählt jedes Mal das kleinste Element aus und verschiebt es an seine richtige Stelle.
  • Bubble Sort vergleicht Paare benachbarter Werte nacheinander und vertauscht sie, wenn sie in der falschen Reihenfolge sind. Dies wird so lange fortgesetzt, bis die Liste sortiert ist.
  • Merge Sort teilt die Liste rekursiv in zwei Teile und fügt die kleineren Listen in der richtigen Reihenfolge wieder zu einer größeren zusammen.

In dieser Aufgabe werden Sie drei (kompilierte!) Sortierprogramme analysieren, um herauszufinden, welche Algorithmen jeweils verwendet werden.

Halten Sie Ihre Antworten zusammen mit einer Erklärung für jedes Programm in einer Datei namens answers.txt in einem Ordner namens sort fest, indem Sie die mit TODO markierten Leerstellen ausfüllen. Diese TODOs finden Sie in der Datei answers.txt, die Sie zusammen mit den kompilierten Programmen herunterladen. Beachten Sie hierzu die Hinweise unter Aufgabenmaterial.

Aufgabenmaterial

Für diese Aufgabe benötigen Sie Programme, die von uns zur Verfügung gestellt werden. Sie erhalten drei bereits kompilierte C-Programme, sort1, sort2 und sort3, sowie mehrere .txt-Dateien zur Eingabe und eine weitere Datei, answers.txt, in die Sie Ihre Antworten schreiben können. In sort1, sort2 und sort3 ist jeweils ein anderer Sortieralgorithmus implementiert: Selection Sort, Bubble Sort und Merge Sort (allerdings nicht unbedingt in dieser Reihenfolge). Ihre Aufgabe ist es, herauszufinden, welcher Sortieralgorithmus in welchem Programm verwendet wird.

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://inf.zone/download/exercises/03/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/ $

Hilfestellung

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

Untersuchen Sie die .txt-Dateien
  • Es werden Ihnen mehrere .txt-Dateien zur Verfügung gestellt. Diese Dateien enthalten n Zeilen mit Werten, die entweder umgedreht, gemischt oder sortiert sind.
    • Zum Beispiel enthält reversed10000.txt 10000 Zeilen mit Zahlen, deren Sortierung umgedreht ist (also von 10000 zu 1 sortiert, statt von 1 zu 10000), während random50000.txt 50000 Zeilen mit Zahlen in zufälliger Reihenfolge enthält.
  • Die verschiedenen Arten von .txt-Dateien können Ihnen helfen, die richtige Sortierung zu finden. Überlegen Sie, wie die einzelnen Algorithmen bei einer bereits sortierten Liste abschneiden. Wie bei einer umgekehrten Liste? Oder einer gemischten Liste? Es kann hilfreich sein, eine kleinere Liste jedes Typs durchzuarbeiten und jeden Sortiervorgang zu durchlaufen.
Messen Sie die Zeit für jede Sortierung mit verschiedenen Eingaben
  • Um die Textdateien zu sortieren, führen Sie im Terminal ./[Programmname] [Textdatei.txt] aus. Stellen Sie sicher, dass Sie cd benutzt haben, um in das Verzeichnis sort zu wechseln!
    • Um zum Beispiel reversed10000.txt mit sort1 zu sortieren, führen Sie ./sort1 reversed10000.txt aus.
  • Es ist sinnvoll, die für die Sortierung benötigte Zeit zu messen. Dazu führen Sie time ./[sort_file] [text_file.txt] aus.
    • Zum Beispiel könnten Sie mit time ./sort1 reversed10000.txt die Zeit messen, die sort1 benötigt, um 10.000 umgekehrt sortierte Zahlen zu sortieren. Am Ende der Ausgabe Ihres Terminals können Sie unter real die “echte” Zeit sehen, die bei der Ausführung des Programms tatsächlich verstrichen ist.
ℹ️
Mit Strg+Shift+C und Strg+Shift+V (bei Windows, ansonsten rechter Mausklick in das Terminalfenster) kann man Text in die Kommandozeile kopieren. Zuvor genutzte Befehle kann man mit den Pfeiltasten (hoch/runter) oder Strg+R erneut aufrufen.

Testen

Korrektheit

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

check50 -l cs50/problems/2024/x/sort
Mehrheitswahl