# 3. Algorithmen

Quelle: https://inf.zone/lectures/3-algorithmen/

Suchen: Lineare Suche, Binäre Suche. Sortieren: Bubble Sort, Selection Sort, Merge Sort. Asymptotische Notation: \(O\), \(\Omega\). Rekursion.

![landscape](https://inf.zone/lectures/3-algorithmen/lec3-still.jpg "Algorithmus zum Zählen im Hörsaal")

## Video

*Das Video ist noch nicht verfügbar. Die Aufzeichnung steht ein bis zwei Wochen nach der Vorlesung hier.*

## Material

Die Folien stehen ein bis zwei Tage nach der Vorlesung hier.

- [Notizen](https://inf.zone/lectures/3-algorithmen/notes3)
- [Code](https://inf.zone/download/lectures/3-algorithmen/3-src.zip)

## Zugehörige Inhalte

### Shorts

Die Shorts vertiefen einzelne Themen der Vorlesung. Schauen Sie sie gezielt dort an, wo Sie bei einer Übungsaufgabe nicht weiterkommen, und programmieren Sie die Beispiele darin nach. „Die drei Extra-Minuten“ am Ende gehen meist über die Basis hinaus (Kür); was davon zur Basis gehört, steht auf der Seite des Shorts.

- [3.1 Lineare Suche](https://inf.zone/lectures/3-algorithmen/short-3-1-lineare-suche/) (8 min): Lineare Suche: Pseudocode, Beispiel, Worst und Best Case, Laufzeit O(n) und Ω(1), Vor- und Nachteile, Implementierung in C
- [3.2 Binäre Suche](https://inf.zone/lectures/3-algorithmen/short-3-2-binaere-suche/) (14 min): Binäre Suche im sortierten Array nach „Teile und herrsche“: Pseudocode, Beispiel, O(log n) und Ω(1), Wahl der Mitte, 20 Questions
- [3.3 Bubble Sort](https://inf.zone/lectures/3-algorithmen/short-3-3-bubble-sort/) (11 min): Bubble Sort: benachbarte Elemente vertauschen, Tauschzähler, Pseudocode, Beispiel, O(n²) und Ω(n), Anzahl der Vergleiche
- [3.4 Selection Sort](https://inf.zone/lectures/3-algorithmen/short-3-4-selection-sort/) (5 min): Selection Sort: kleinstes Element des unsortierten Teils suchen und nach vorne tauschen; Pseudocode, Beispiel, O(n²) und Ω(n²), Minimumsuche in C
- [3.5 Rekursion](https://inf.zone/lectures/3-algorithmen/short-3-5-rekursion/) (13 min): Rekursion: Basisfall und rekursiver Fall, Fakultät rekursiv und iterativ, Fibonacci, Collatz-Vermutung, Call Stack, Stack Overflow
- [3.6 Merge Sort](https://inf.zone/lectures/3-algorithmen/short-3-6-merge-sort/) (11 min): Merge Sort: teilen, rekursiv sortieren, zusammenführen (merge); Rekursionsbaum und Schrittliste, O(n log n), merge in C mit drei Markern