# Sortieren

Quelle: https://dev.inf.zone/exercises/05/sort/

## Aufgabe

**Auf einen Blick**

- **Was:** Sie finden heraus, welches der drei bereits kompilierten Programme `sort1`, `sort2` und `sort3` welchen Sortieralgorithmus verwendet: Selection Sort, Bubble Sort oder Merge Sort (nicht unbedingt in dieser Reihenfolge).
- **Material:** die drei Programme, Textdateien mit Zahlen und `answers.txt` (siehe [Aufgabenmaterial](#aufgabenmaterial)).
- **Vorgehen:** die Programme mit verschiedenen Dateien laufen lassen und die Zeit messen, etwa `time ./sort1 reversed10000.txt`.
- **Abgabe:** In `answers.txt` im Ordner `sort` ersetzen Sie die `TODO`s: je Programm der Algorithmus und eine kurze Begründung.

### So unterscheiden sich die drei Verfahren

Alle drei Algorithmen kennen Sie aus der [Vorlesung](https://dev.inf.zone/lectures/3-algorithmen/) 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:

1. [Selection Sort](https://dev.inf.zone/lectures/3-algorithmen/short-3-4-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.
2. [Bubble Sort](https://dev.inf.zone/lectures/3-algorithmen/short-3-3-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.
3. [Merge Sort](https://dev.inf.zone/lectures/3-algorithmen/short-3-6-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](https://dev.inf.zone/extras/setup/).

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

```bash
$
```

Geben Sie dann

```bash
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

```bash
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

```bash
rm sort.zip
```

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

```bash
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:

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

## Abgeben

Geben Sie im Ordner `sort` ab:

```bash
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`](https://dev.inf.zone/faq/uebung-solutions/#inf-installieren).