Praktisch immer: Bubblesort (zum Aufwaermen), Quicksort und Mergesort (die zwei wichtigen O(n log n)-Algorithmen). Insertion Sort kommt manchmal noch dazu. Was du wissen musst: Idee in einem Satz, Pseudocode oder Java-Code, Best/Worst/Average-Laufzeit, ob in-place und ob stabil. Quicksort ist Standard im Vergleich, Mergesort ist Standard wenn Stabilitaet zaehlt.
Was bedeutet O(n log n)?
Die Big-O-Notation beschreibt das Wachstum der Laufzeit eines Algorithmus relativ zur Eingabegroesse n. O(n log n) heisst: bei doppelter Eingabe nicht doppelte sondern etwas mehr als doppelte Laufzeit. Konkret: bei n=1000 sind es ca. 10000 Operationen (1000 * 10), bei n=1 Million ca. 20 Millionen. Das ist schnell genug fuer die meisten praktischen Probleme.
Wann nehme ich Binaere Suche, wann Lineare?
Binaere Suche braucht zwingend sortierte Daten und ist O(log n). Lineare Suche funktioniert auf unsortierten Daten und ist O(n). Wenn du eine Liste hast die du oft durchsuchst, lohnt es sich einmalig zu sortieren (O(n log n)) und dann immer binaer zu suchen. Bei einer einmaligen Suche auf unsortierten Daten ist linear schneller als sortieren-plus-suchen.
Muss ich Algorithmen auswendig lernen?
Nein, aber du musst sie verstehen. In der Klausur wird oft Pseudocode oder Java-Code zum Vervollstaendigen gegeben oder du sollst die Idee in eigenen Worten erklaeren. Lerne die Idee, eine Beispiel-Spur (mit konkreten Zahlen Schritt fuer Schritt) und die Laufzeit. Wer nur Code auswendig lernt, scheitert an Variations-Aufgaben.
Quicksort vs Mergesort, was ist Standard in der Klausur?
Beide sind Pflicht. Quicksort ist meist schneller in der Praxis (in-place, gute Cache-Performance), aber Worst-Case O(n^2). Mergesort ist immer O(n log n), aber braucht O(n) zusaetzlichen Speicher und ist nicht in-place. In der Klausur wird oft das Verhalten bei sortierten Eingaben gefragt, da ist naive Quicksort schlecht (O(n^2)), Mergesort gleich gut wie immer.
