Strukturierung: Rekursive Funktionsaufrufe
Rekursion in Racket
Da rein funktionale Sprachen keine Schleifenstrukturen wie while oder for unterstützen, ist die Rekursion hier besonders wichtig, da diese eine Möglichkeit für Iterationen bietet. Rekursion ist jedoch auch in vielen anderen Fällen nützlich, da durch Rekursion Probleme in kleinere, lösbare Teilprobleme zerlegt werden können.
select-index für die Selektion eines Listenelements:
- Wir wissen, dass wir mit
firstdas erste Element einer Liste in Racket erhalten. Unser Basisfall stellt damit den Fall dar, dass unser gesuchtes Element genau auf Index 0 liegt. - Ist ersteres nicht der Fall, können wir durch einen Reduktionsschritt das Problem auf die Betrachtung einer gekürzten Liste ohne das vorherige erste Element herunterbrechen.
- Wir wiederholen den Reduktionsschritt nun so lange, bis wir den Basisfall erreicht haben, in welchem das gesuchte Element auf Index 0 liegt.
(: select-index ((list-of any) natural -> any))
(check-expect (select-index (list 10 20 30) 2) 30)
(define select-index
(lambda (l i)
(cond
([= i 0] (first l))
(else (select-index (rest l) (- i 1))))))
(Hinweis: die Funktion fängt zur besseren Übersichtlichkeit keine unzulässigen Indizes ab)
Aufgabe 1: Gehaltsanalyse auf einer unsortierten Liste
Zur Gehaltsanalyse legt auch Firma-B eine Liste mit den Jahresgehältern aller 80 Mitarbeitenden vor:
(define firmaB
(list 6680 48000 55000 34000 6680 60000 42000 6680 42000 55000 6680 48000 55000 6680 42000 60000 70000 48000 34000 34000 6680
48000 42000 55000 34000 42000 42000 42000 60000 48000 55000 48000 48000 55000 48000 77000 48000 55000 60000 48000 42000
34000 55000 55000 6680 6680 48000 6680 55000 90000 34000 48000 55000 42000 70000 55000 48000 6680 42000 90000 48000
34000 48000 6680 55000 42000 42000 34000 60000 55000 42000 48000 115000 42000 55000 55000 48000 55000 48000 42000))
(a) Bestimme die ersten 7 Elemente sowie den Medianwert der Liste firmaB.
Beurteile, wie aussagekräftig die erhaltenen Daten sind. Achte dabei auf die Anordnung
der Listenelemente.
(b) Schreibe eine Sortierfunktion, die Zahlenlisten aufsteigend ordnet.
Benutze als Sortieralgorithmus entweder Insertion Sort oder Merge Sort.
Insertion Sort:
Mit Insertion Sort sortieren wir eine Liste, indem wir ein neues Element an die richtige Stelle in eine vorsortierte Liste einfügen.
Schematisch haben wir zu Beginn einer Sortierung eine leere Liste und eine unsortierte Liste. Wir füllen die leere Liste, indem wir
immer das erste Element der unsortierten Liste an die richtige stelle der neuen (anfänglich leeren) Liste einfügen. Im nächsten
Schritt betrachten wir den Rest der unsortierten Liste.
$empty \leftarrow (list\ 1\ 0\ \text{-}4\ 2\ 7\ 6)$
$(list\ 1) \leftarrow (list\ 0\ \text{-}4\ 2\ 7\ 6)$
$(list\ 0\ 1) \leftarrow (list\ \text{-}4\ 2\ 7\ 6)$
$(list\ \text{-}4\ 0\ 1) \leftarrow (list\ 2\ 7\ 6)$
$(list\ \text{-}4\ 0\ 1\ 2) \leftarrow (list\ 7\ 6)$
$(list\ \text{-}4\ 0\ 1\ 2\ 7) \leftarrow (list\ 6)$
$(list\ \text{-}4\ 0\ 1\ 2\ 6\ 7)$
| Insertion Sort | Laufzeit |
|---|---|
| Average-Case | $O(n^2)$ |
| Best-Case | $O(n)$ |
| Worst-Case | $O(n^2)$ |
Merge Sort:
Der Algorithmus für Merge Sort ist zwar etwas komplizierter zu implementieren als der von Insertion Sort, dafür ist
der Algorithmus aber auch durchschnittlich effizienter.
Merge Sort arbeitet nach dem Prinzip Teile und Herrsche. Der Algorithmus ist dabei in zwei Phasen unterteilt: eine
Split‑Phase und eine Merge‑Phase.
In der Split‑Phase wird die Liste solange in zwei (möglichst gleich große) Teile zerlegt, bis nur noch Listen mit einem Element übrig sind. In der Merge‑Phase werden diese einzelnen Elemente nun paarweise sortiert wieder zusammengefügt. Im Sortierprozess der Merge‑Phase werden immer zwei Listen miteinander verglichen. Dabei wird immer das erste Element der Listen verglichen. Das kleinste der beiden Elemente wird zu einer neuen sortierten Liste angefügt. Im nächsten Vergleichsprozess betrachten wir den Rest der unsortierten Liste, aus der das vorherig kleinste Element stammt.
Schematischer Ablauf von Merge Sort:
Beispielhafter Vergleichsprozess zweier Listen: $(list\ 2\ 7)$ und $(list\ \text{-}1\ 6)$
- Vergleiche $2$ und $\text{-}1$
$empty \leftarrow (list\ 2\ 7)\ (list\ \text{-}1\ 6)$
- Vergleiche $2$ und $6$
$(list\ \text{-}1) \leftarrow (list\ 2\ 7)\ (list\ 6)$
- Vergleiche $7$ und $6$
$(list\ \text{-}1\ 2) \leftarrow (list\ 7)\ (list\ 6)$
- Füge $7$ an - da kein weiteres Element zum Vergleichen mehr vorhanden ist
$(list\ \text{-}1\ 2\ 6) \leftarrow (list\ 7)\ empty$
$(list\ \text{-}1\ 2\ 6\ 7)$
| Merge Sort | Laufzeit |
|---|---|
| Average-Case | $O(n \cdot log(n))$ |
| Best-Case | $O(n \cdot log(n))$ |
| Worst-Case | $O(n \cdot log(n))$ |
(c) Bestimme die vier höchsten und zwölf geringsten Jahresgehälter in Firma-B.
(d) Vergleiche Firma-A und Firma-B. Welche der Firmen hat ein höheres Median-Gehalt, welche den höheren Mittelwert?
(e) Firma-B beschäftigt mehrere Angestellte auf Minijob-Basis (Stand 2025: die Personen, deren Jahresgehalt 6680 € beträgt). Rechne sämtliche Minijob-Angestellten der Firma-B heraus und vergleiche die Firmen wie in (c) beschrieben anschließend erneut.
