Einführung in die Programmierung - Exam.pdf

Aufgabe 1)

Du sollst einige Konzepte des imperativen Programmierens umsetzen und analysieren. Unten findest Du die nötigen Informationen und Aufgabenstellungen.Schreibe ein Programm in Python, das die Fakultät einer Ganzzahl berechnet. Verwende dafür Schleifen und wende die grundlegenden Konzepte des imperativen Programmierens an.Hier sind einige Hinweise:

• Verwende eine Schleife, um die Fakultät zu berechnen.
• Stelle sicher, dass Du Variablen zur Speicherung von Zwischenergebnissen verwendest.
• Implementiere eine Funktion, die die Berechnung übernimmt.
• Denke daran, dass die Fakultät von 0 definiert ist und gleich 1 ist.

a)

(a) Implementiere die Funktion berechne_fakultaet(n), die die Fakultät der Ganzzahl n berechnet und zurückgibt. Nutze eine for-Schleife und die Variablendeklaration.Beispielausgabe:

berechne_fakultaet(5)  # sollte 120 zurückgeben

Lösung:

Lösung der Aufgabe:Hier ist die Implementierung der Funktion berechne_fakultaet(n) in Python. Diese Funktion verwendet eine for-Schleife, um die Fakultät einer gegebenen Ganzzahl n zu berechnen.

• Zuerst überprüfen wir, ob die Eingabe 0 ist, da die Fakultät von 0 per Definition 1 ist.
• Wir initialisieren eine Variable ergebnis, um das Zwischenergebnis der Berechnung zu speichern, und setzen sie auf 1.
• Dann verwenden wir eine for-Schleife, um alle Zahlen von 1 bis n zu durchlaufen, und multiplizieren ergebnis mit der aktuellen Zahl in jeder Iteration.
• Am Ende geben wir das ergebnis zurück.

Hier ist der Python-Code dafür:

def berechne_fakultaet(n):    # Fakultät von 0 ist 1    if n == 0:        return 1        # Zwischenergebnis Variable initialisieren    ergebnis = 1        # For-Schleife, um die Fakultät zu berechnen    for i in range(1, n + 1):        ergebnis *= i        return ergebnis# Beispielaufrufprint(berechne_fakultaet(5))  # sollte 120 zurückgeben

Die Ausgabe des Beispielaufrufs berechne_fakultaet(5) sollte 120 sein, da die Fakultät von 5 (5!) gleich 120 ist (5 * 4 * 3 * 2 * 1 = 120).

b)

(b) Analysiere die Zeitkomplexität Deiner implementierten Funktion. Begründe Deine Antwort mithilfe der großen O-Notation. Gib eine detaillierte Beschreibung der Zeitkomplexität der Schleifenstruktur in Deiner Funktion.

Lösung:

Analyse der Zeitkomplexität:Um die Zeitkomplexität der Funktion berechne_fakultaet(n) zu analysieren, müssen wir die Ausführungsschritte und Schleifen in der Funktion betrachten.

• Die Funktion überprüft zunächst, ob n gleich 0 ist. Diese Überprüfung ist eine konstante Operation und hat somit eine Zeitkomplexität von O(1).
• Die Funktion initialisiert eine Variable ergebnis auf 1. Dies ist ebenfalls eine konstante Operation mit einer Zeitkomplexität von O(1).
• Der wesentliche Teil der Funktion ist die for-Schleife. Diese Schleife läuft von 1 bis n und führt in jeder Iteration eine Multiplikation durch. Die Anzahl der Iterationen ist daher proportional zu n.

Schleifenstruktur:Die Schleife durchläuft alle ganzzahligen Werte von 1 bis n, also n Iterationen:

for i in range(1, n + 1):    ergebnis *= i

In jeder Iteration wird eine Multiplikation durchgeführt, was ebenfalls eine konstante Zeitoperation ist. Da die Schleife insgesamt n Mal läuft und jede Iteration konstanten Zeitaufwand benötigt, beträgt die Zeitkomplexität dieser Schleifenstruktur O(n).Gesamte Zeitkomplexität der Funktion:

• Überprüfung, ob n gleich 0 ist: O(1)
• Initialisierung der Variable ergebnis: O(1)
• for-Schleife: O(n)

Die dominierende Komponente ist die for-Schleife, daher können wir die Gesamtlaufzeit der Funktion berechne_fakultaet(n) als O(n) darstellen.In der großen O-Notation wird die Zeitkomplexität der Funktion also durch O(n) beschrieben.Zusammenfassend, die Zeitkomplexität der Funktion berechne_fakultaet(n) ist O(n), da die Funktion eine Schleife enthält, die proportional zur Eingabegröße n läuft.

Aufgabe 2)

In einem Unternehmen sollen Mitarbeiter und ihre Rollen in einem hierarchischen System modelliert werden. Dabei sollen verschiedene Arten von Mitarbeitern unterschiedliche Methoden implementieren. Verwende das Konzept der Vererbung, um die Hierarchie abzubilden. Gehe dabei von einer allgemeinen Klasse 'Mitarbeiter' aus, die grundlegende Eigenschaften und Methoden definiert. Spezifische Mitarbeiterrollen wie 'Manager' und 'Entwickler' sollen von dieser Basis-Klasse erben und zusätzliche Attribute und Methoden hinzufügen.

a)

Definiere eine Klasse `Mitarbeiter` mit den Attributen `name` und `gehalt`. Die Klasse soll eine Methode `arbeite` enthalten, die am besten `NotImplementedError` auslöst. Implementiere diese Klasse in Python.

Lösung:

Um die Klasse Mitarbeiter zu definieren, werden wir die Attribute name und gehalt hinzufügen und eine Methode arbeite implementieren, die einen NotImplementedError auslöst. Hier ist die Implementation in Python:

class Mitarbeiter:    def __init__(self, name, gehalt):        self.name = name        self.gehalt = gehalt        def arbeite(self):        raise NotImplementedError("Diese Methode sollte in der abgeleiteten Klasse überschrieben werden")

• __init__: Der Konstruktor der Klasse, der die Attribute name und gehalt initialisiert.
• arbeite: Eine Methode, die einen NotImplementedError auslöst, um sicherzustellen, dass sie in den abgeleiteten Klassen überschrieben wird.

b)

Erstelle eine Unterklasse `Manager`, die von `Mitarbeiter` erbt. Diese Klasse soll ein zusätzliches Attribut `abteilung` und eine Methode `arbeite` haben, die einen String zurückgibt, der den Manager und seine Abteilung beschreibt. Implementiere die Klasse in Python.

Lösung:

Um die Unterklasse Manager zu definieren, die von Mitarbeiter erbt, werden wir zusätzlich das Attribut abteilung und die Methode arbeite implementieren. Hier ist die Implementation in Python:

class Manager(Mitarbeiter):    def __init__(self, name, gehalt, abteilung):        super().__init__(name, gehalt)        self.abteilung = abteilung        def arbeite(self):        return f"Manager {self.name} leitet die Abteilung {self.abteilung}."

• __init__: Der Konstruktor der Klasse Manager, der das Attribut abteilung initialisiert und den Konstruktor der Basis-Klasse Mitarbeiter aufruft.
• arbeite: Eine Methode, die einen String zurückgibt, der den Manager und seine Abteilung beschreibt.

c)

Entwickle eine zweite Unterklasse `Entwickler`, die ebenfalls von `Mitarbeiter` erbt. Sie soll ein zusätzliches Attribut `programmiersprache` und eine Methode `arbeite` haben, die einen String zurückgibt, der den Entwickler und seine Programmiersprache beschreibt. Implementiere die Klasse in Python. Erstelle eine Liste von Mitarbeitern, die mindestens einen `Manager` und einen `Entwickler` enthält, und rufe die Methode `arbeite` für jeden Mitarbeiter auf.

Lösung:

Um die Unterklasse Entwickler zu definieren, die von Mitarbeiter erbt, werden wir zusätzlich das Attribut programmiersprache und die Methode arbeite implementieren. Dann erstellen wir eine Liste von Mitarbeitern, die mindestens einen Manager und einen Entwickler enthält, und rufen die Methode arbeite für jeden Mitarbeiter in der Liste auf. Hier ist die Implementation in Python:

class Entwickler(Mitarbeiter):    def __init__(self, name, gehalt, programmiersprache):        super().__init__(name, gehalt)        self.programmiersprache = programmiersprache        def arbeite(self):        return f"Entwickler {self.name} programmiert in {self.programmiersprache}."

# Erstelle eine Liste von Mitarbeiternmitarbeiter_liste = [    Manager("Anna Schmidt", 75000, "Verkauf"),    Entwickler("Max Mustermann", 60000, "Python")]# Rufe die Methode 'arbeite' für jeden Mitarbeiter auf for mitarbeiter in mitarbeiter_liste:    print(mitarbeiter.arbeite())

• __init__: Der Konstruktor der Klasse Entwickler, der das Attribut programmiersprache initialisiert und den Konstruktor der Basis-Klasse Mitarbeiter aufruft.
• arbeite: Eine Methode, die einen String zurückgibt, der den Entwickler und seine Programmiersprache beschreibt.
• mitarbeiter_liste: Eine Liste, die mindestens einen Manager und einen Entwickler enthält.
• for-Schleife: Eine Schleife, die die Methode arbeite für jeden Mitarbeiter in der mitarbeiter_liste aufruft und das Ergebnis ausgibt.

Aufgabe 3)

Funktionales Programmieren in Python:Das funktionale Paradigma in der Programmierung behandelt Funktionen als erste Bürger, das bedeutet, Funktionen können als Argumente an andere Funktionen übergeben, als Rückgabewerte verwendet und wie jede andere Datenform behandelt werden. Ein wichtiger Aspekt dabei ist die Rekursion, bei der sich Funktionen selbst aufrufen. Wir werden in diesem Kontext unter anderem praktische Anwendungen wie die Berechnung von Fakultäten und der Summe einer Liste erarbeiten.

a)

Schreibe eine rekursive Python-Funktion factorial, die die Fakultät einer gegebenen Zahl n berechnet. Implementiere die Funktion so, dass sie den Basisfall f(0) = 1 und den rekursiven Schritt f(n) = n * f(n-1) berücksichtigt.

def factorial(n):    # Your code here

Lösung:

Funktionales Programmieren in Python:Das funktionale Paradigma in der Programmierung behandelt Funktionen als erste Bürger, das bedeutet, Funktionen können als Argumente an andere Funktionen übergeben, als Rückgabewerte verwendet und wie jede andere Datenform behandelt werden. Ein wichtiger Aspekt dabei ist die Rekursion, bei der sich Funktionen selbst aufrufen. Wir werden in diesem Kontext unter anderem praktische Anwendungen wie die Berechnung von Fakultäten und der Summe einer Liste erarbeiten.Hier ist die Lösung der Teilaufgabe:Schreibe eine rekursive Python-Funktion factorial, die die Fakultät einer gegebenen Zahl n berechnet. Implementiere die Funktion so, dass sie den Basisfall f(0) = 1 und den rekursiven Schritt f(n) = n * f(n-1) berücksichtigt.Implementierung der Funktion:

def factorial(n):    if n == 0:        # Basisfall: f(0) = 1        return 1    else:        return n * factorial(n-1)  # Rekursiver Schritt: f(n) = n * f(n-1)

b)

Erkläre mit Hilfe von mathematischen Formeln, wie die rekursive Funktion aus dem ersten Teil aufgerufen wird und wie sich die Werte entwickeln, wenn factorial(5) aufgerufen wird. Zeichne den Evaluationsbaum der Aufrufe und benutze dafür LaTeX für mathematische Formeln.

• Starte mit der Ausgangsfunktion factorial(5)
• Zeige alle rekursiven Aufrufe bis zum Basisfall factorial(0)
• Berechne Schritt für Schritt die Rückgabe der Funktion und stelle dies durch die entsprechenden Formeln dar.

Lösung:

Funktionales Programmieren in Python:Das funktionale Paradigma in der Programmierung behandelt Funktionen als erste Bürger, das bedeutet, Funktionen können als Argumente an andere Funktionen übergeben, als Rückgabewerte verwendet und wie jede andere Datenform behandelt werden. Ein wichtiger Aspekt dabei ist die Rekursion, bei der sich Funktionen selbst aufrufen. Wir werden in diesem Kontext unter anderem praktische Anwendungen wie die Berechnung von Fakultäten und der Summe einer Liste erarbeiten.Erklärungen zu den rekursiven Aufrufen der Funktion factorial und wie sich die Werte entwickeln, wenn factorial(5) aufgerufen wird, sind wie folgt:

• Starte mit der Ausgangsfunktion factorial(5)
• Zeige alle rekursiven Aufrufe bis zum Basisfall factorial(0)
• Berechne Schritt für Schritt die Rückgabe der Funktion und stelle dies durch die entsprechenden Formeln dar.

### Evaluationsschritte der rekursiven Funktion1. Start mit der Ausgangsfunktion:\[factorial(5)\]2. Rekursionsschritte:\[\begin{align*} factorial(5) &= 5 * factorial(4) \ factorial(4) &= 4 * factorial(3) \ factorial(3) &= 3 * factorial(2) \ factorial(2) &= 2 * factorial(1) \ factorial(1) &= 1 * factorial(0) \ factorial(0) &= 1 \end{align*}\]3. Jetzt berechnen wir die Rückgaben Schritt für Schritt:\[\begin{align*} factorial(1) &= 1 * factorial(0) = 1 * 1 = 1 \ factorial(2) &= 2 * factorial(1) = 2 * 1 = 2 \ factorial(3) &= 3 * factorial(2) = 3 * 2 = 6 \ factorial(4) &= 4 * factorial(3) = 4 * 6 = 24 \ factorial(5) &= 5 * factorial(4) = 5 * 24 = 120 \end{align*}\]4. Der Evaluationsbaum der Aufrufe sieht folgendermaßen aus:\[\begin{array}{ccccccc} & & & factorial(5) & & & \ & & factorial(4) & & & 5 & & \ & factorial(3) & & & & 4 & & \ factorial(2) & & & & 3 & & \ factorial(1) & & & & 2 & & \ factorial(0)=1 & & & & 1 & & \ \end{array}\]

c)

Schreibe eine Funktion list_sum, die die Summe aller Elemente in einer Liste rekursiv berechnet. Die Basisbedingung soll eine leere Liste sein, die Summe davon ist 0. Der rekursive Schritt addiert das erste Element der Liste zur Summe der restlichen Liste.

def list_sum(lst):    # Your code here

Lösung:

Funktionales Programmieren in Python:Das funktionale Paradigma in der Programmierung behandelt Funktionen als erste Bürger, das bedeutet, Funktionen können als Argumente an andere Funktionen übergeben, als Rückgabewerte verwendet und wie jede andere Datenform behandelt werden. Ein wichtiger Aspekt dabei ist die Rekursion, bei der sich Funktionen selbst aufrufen. Wir werden in diesem Kontext unter anderem praktische Anwendungen wie die Berechnung von Fakultäten und der Summe einer Liste erarbeiten.Hier die Lösung für die Teilaufgabe, eine Funktion list_sum zu erstellen, die die Summe aller Elemente in einer Liste rekursiv berechnet:

def list_sum(lst):    if len(lst) == 0:        # Basisfall: Eine leere Liste hat die Summe 0        return 0    else:        # Rekursiver Schritt: Das erste Element wird zur Summe der restlichen Liste hinzugefügt        return lst[0] + list_sum(lst[1:])

d)

Diskutiere die Vor- und Nachteile von rekursiven Funktionen in Bezug auf Speicherverbrauch und Performance im Vergleich zu iterativen Lösungen. Erkläre dies anhand eines Beispiels, wie der Berechnung der Fibonacci-Zahlen.

• Implementiere eine rekursive Funktion für die Fibonacci-Zahlen:

  def fibonacci(n):    if n <= 1:        return n    else:        return fibonacci(n-1) + fibonacci(n-2)

• Beschreibe, wie der Speicherstack wächst und welche Probleme auftreten könnten.
• Vergleiche die Effizienz dieser Implementierung mit einer iterativen Lösung.

Lösung:

Funktionales Programmieren in Python:Das funktionale Paradigma in der Programmierung behandelt Funktionen als erste Bürger, das bedeutet, Funktionen können als Argumente an andere Funktionen übergeben, als Rückgabewerte verwendet und wie jede andere Datenform behandelt werden. Ein wichtiger Aspekt dabei ist die Rekursion, bei der sich Funktionen selbst aufrufen. Wir werden in diesem Kontext unter anderem praktische Anwendungen wie die Berechnung von Fakultäten und der Summe einer Liste erarbeiten.### Implementierung einer rekursiven Funktion für die Fibonacci-Zahlen:

def fibonacci(n):    if n <= 1:        return n    else:        return fibonacci(n-1) + fibonacci(n-2)

### Diskussion der Vor- und Nachteile rekursiver Funktionen im Vergleich zu iterativen Lösungen:#### Vorteile rekursiver Funktionen:

• Klarheit und Einfachheit: Rekursive Funktionen sind oft einfacher und eleganter, besonders bei Problemen, die sich natürlich rekursiv ausdrücken lassen.
• Reduzierung von Code: Weniger Codezeilen im Vergleich zu iterativen Lösungen.

#### Nachteile rekursiver Funktionen:

• Hoher Speicherverbrauch: Jede Rekursionsebene benötigt Speicherplatz im Aufrufstack, was zu einem Stack Overflow führen kann, wenn die Rekursion zu tief wird.
• Schlechtere Performance: Manche rekursiven Algorithmen, wie die naive Berechnung der Fibonacci-Zahlen, haben eine exponentielle Laufzeit, da viele Berechnungen wiederholt ausgeführt werden.

### Beispiel: Berechnung der Fibonacci-Zahlen#### Speicherstack und Probleme:Wenn wir die rekursive Funktion fibonacci(n) verwenden, wächst der Speicherstack mit jedem rekursiven Aufruf. Für größere Werte von n wird der Stack sehr tief, was zu einem Stack Overflow führen kann. Zum Beispiel:

• fibonacci(5) ruft auf fibonacci(4) und fibonacci(3)
• fibonacci(4) ruft auf fibonacci(3) und fibonacci(2)
• .... und so weiter.

Der Speicherstack kann sehr tief werden, was zu einem Stack Overflow führen könnte.#### Effizienz im Vergleich zu einer iterativen Lösung:Die rekursive Implementierung der Fibonacci-Funktion hat eine exponentielle Zeitkomplexität O(2^n), da viele Berechnungen wiederholt werden. Dagegen hat eine iterative Lösung eine lineare Zeitkomplexität O(n) und ist daher viel effizienter.### Iterative Implementierung der Fibonacci-Funktion:

def fibonacci_iterative(n):    a, b = 0, 1    for _ in range(n):        a, b = b, a + b    return a

• Effizienz: Die iterative Lösung hat eine lineare Zeitkomplexität O(n) und einen konstanten Speicherbedarf O(1).
• Sicherheit: Es gibt keine Gefahr eines Stack Overflow, da keine tiefen Rekursionsketten vorhanden sind.

Aufgrund dieser Überlegungen sind iterative Lösungen oft bevorzugt bei Problemen mit tiefen Rekursionen. Dennoch haben rekursive Lösungen ihre Daseinsberechtigung, besonders wenn sie den Code klarer und verständlicher machen.

Aufgabe 4)

Deine Aufgabe besteht darin, verschiedene Sortier- und Suchalgorithmen zu analysieren und ihre Eigenschaften zu vergleichen. Betrachte die folgenden Algorithmen:

• Bubble Sort
• Merge Sort
• Quicksort
• Heapsort
• Lineare Suche
• Binäre Suche

Du wirst die Algorithmen hinsichtlich ihrer Laufzeiten im besten, durchschnittlichen und schlechtesten Fall bewerten, sowie ihre Stabilität und In-Situ-Eigenschaften untersuchen. Schließlich sollst du mögliche Optimierungen diskutieren, wie die Wahl des Pivot-Elements für Quicksort und die Kombination von Algorithmen.

a)

Teilaufgabe 1: Berechne und vergleiche die zeitliche Komplexität der Sortieralgorithmen Bubble Sort, Merge Sort, Quicksort und Heapsort im besten, durchschnittlichen und schlechtesten Fall. Stelle Deine Ergebnisse in einer Tabelle dar. Erläutere außerdem, ob jeder Algorithmus stabil und in-situ ist.

Lösung:

Teilaufgabe 1: Berechne und vergleiche die zeitliche Komplexität der Sortieralgorithmen Bubble Sort, Merge Sort, Quicksort und Heapsort im besten, durchschnittlichen und schlechtesten Fall. Stelle Deine Ergebnisse in einer Tabelle dar. Erläutere außerdem, ob jeder Algorithmus stabil und in-situ ist.

Algorithmus	Best Case	Average Case	Worst Case	Stabil	In-Situ
Bubble Sort	O(n) (wenn die Liste bereits sortiert ist)	O(n^2)	O(n^2)	Ja	Ja
Merge Sort	O(n log n)	O(n log n)	O(n log n)	Ja	Nein
Quicksort	O(n log n)	O(n log n)	O(n^2)	Nein	Ja
Heapsort	O(n log n)	O(n log n)	O(n log n)	Nein	Ja

• Bubble Sort: Bubble Sort ist stabil, weil die Reihenfolge von gleichen Elementen erhalten bleibt. Es ist auch ein in-situ Algorithmus, da es keinen zusätzlichen Speicher außer für ein paar Hilfsvariablen benötigt.
• Merge Sort: Merge Sort ist stabil, weil die Reihenfolge von gleichen Elementen erhalten bleibt. Es ist jedoch nicht in-situ, da es zusätzlichen Speicherplatz für die Zwischenarrays benötigt.
• Quicksort: Quicksort ist normalerweise nicht stabil, da die Reihenfolge von gleichen Elementen nicht garantiert ist. Es ist jedoch in-situ, da es sortiert wird, indem Elemente in der ursprünglichen Liste vertauscht werden, ohne zusätzlichen Speicherplatz zu benötigen.
• Heapsort: Heapsort ist nicht stabil, da die Reihenfolge von gleichen Elementen nicht erhalten bleibt. Es ist in-situ, da es direkt im Array sortiert und keinen zusätzlichen Speicherplatz benötigt.

b)

Teilaufgabe 2: Implementiere in Python einen der besprochenen Sortieralgorithmen (Quicksort) und einen Suchalgorithmus (binäre Suche). Verwende dazu folgende Funktionssignatur:

def quicksort(array):  # Implementiere den Quicksort Algorithmus hier def binary_search(array, target):  # Implementiere den binären Suchalgorithmus hier

Beschreibe kurz die Funktionsweise jedes Algorithmus und kommentiere Deinen Code ausführlich.

Lösung:

Teilaufgabe 2: Implementiere in Python einen der besprochenen Sortieralgorithmen (Quicksort) und einen Suchalgorithmus (binäre Suche). Verwende dazu folgende Funktionssignatur:

def quicksort(array):  # Implementiere den Quicksort Algorithmus hier def binary_search(array, target):  # Implementiere den binären Suchalgorithmus hier

Beschreibe kurz die Funktionsweise jedes Algorithmus und kommentiere Deinen Code ausführlich.

• Quicksort: Quicksort ist ein effizienter Sortieralgorithmus, der das Divide-and-Conquer-Prinzip verwendet. Er wählt ein 'Pivot'-Element aus dem Array und partitioniert die anderen Elemente in zwei Teillisten, je nachdem, ob sie kleiner oder größer als das Pivot sind. Diese Teillisten werden dann rekursiv sortiert.
• Binäre Suche: Die binäre Suche ist ein effizienter Suchalgorithmus, der auf sortierten Arrays angewendet wird. Sie halbiert wiederholt den zu durchsuchenden Bereich, indem sie das mittlere Element mit dem Zielwert vergleicht, bis das Ziel gefunden oder der Bereich leer ist.

def quicksort(array):    # Basisfall: Ein leeres Array oder ein Array mit nur einem Element ist bereits sortiert.    if len(array) <= 1:        return array    # Rekursionsfall: Wähle ein Pivot-Element und teile das Array in zwei Teillisten:    pivot = array[len(array) // 2]    left = [x for x in array if x < pivot]    middle = [x for x in array if x == pivot]    right = [x for x in array if x > pivot]    # Rekursiver Aufruf von quicksort für die beiden Teillisten und anschließendes Zusammenfügen.    return quicksort(left) + middle + quicksort(right)

def binary_search(array, target):    left, right = 0, len(array) - 1    while left <= right:        # Berechne das mittlere Element.        mid = (left + right) // 2        # Prüfe, ob das mittlere Element das Ziel ist.        if array[mid] == target:            return mid        # Wenn das mittlere Element größer ist als das Ziel, ignoriere die rechte Hälfte.        elif array[mid] > target:            right = mid - 1        # Wenn das mittlere Element kleiner ist als das Ziel, ignoriere die linke Hälfte.        else:            left = mid + 1    # Das Ziel wurde nicht gefunden.    return -1

• Quicksort: Der Algorithmus sortiert das Array, indem er ein Pivot-Element wählt, das Array in zwei Teillisten aufteilt (eine mit Elementen kleiner und eine mit Elementen größer als das Pivot) und diese Teillisten rekursiv sortiert. Die Gesamtlaufzeit im Durchschnitt ist \text{O}(n \text{log} n).
• Binäre Suche: Der Algorithmus sucht in einem sortierten Array, indem er den Bereich, der durchsucht werden muss, halbiert, basierend auf dem Vergleich des mittleren Elements des Bereichs mit dem Zielwert. Die Gesamtlaufzeit ist \text{O}(\text{log} n).

c)

Teilaufgabe 3: Angenommen, du hast ein Array mit 1000 Elementen, das unsortiert ist. Diskutiere, welche der genannten Sortieralgorithmen du verwenden würdest, um das Array zu ordnen, und begründe Deine Wahl. Außerdem, wenn du wiederholt Elemente in diesem Array suchen müsstest, welche Suchmethode (lineare oder binäre Suche) würdest du anwenden und warum? Gehe dabei auf die Laufzeiten und die Effizienz der Algorithmen ein.

Lösung:

Teilaufgabe 3: Angenommen, Du hast ein Array mit 1000 Elementen, das unsortiert ist. Diskutiere, welche der genannten Sortieralgorithmen Du verwenden würdest, um das Array zu ordnen, und begründe Deine Wahl. Außerdem, wenn Du wiederholt Elemente in diesem Array suchen müsstest, welche Suchmethode (lineare oder binäre Suche) würdest Du anwenden und warum? Gehe dabei auf die Laufzeiten und die Effizienz der Algorithmen ein.

Wahl des Sortieralgorithmus

Für ein unsortiertes Array mit 1000 Elementen würde ich Quicksort bevorzugen:

• Quicksort:
  • Quicksort hat eine durchschnittliche Laufzeit von \(O(n \log n)\).
  • Es ist ein In-Situ-Algorithmus und benötigt daher wenig zusätzlichen Speicher.
  • Quicksort ist in der Praxis oft schneller als andere Algorithmen wie Merge Sort oder Heapsort, obwohl es im schlimmsten Fall \(O(n^2)\) ist. Dieser Fall tritt jedoch selten auf, besonders mit guten Pivot-Strategien.
• Merge Sort:
  • Merge Sort hat im besten, durchschnittlichen und schlechtesten Fall eine Laufzeit von \(O(n \log n)\).
  • Es ist stabil, aber benötigt zusätzlichen Speicher, was für große Arrays nachteilig sein kann.
• Heapsort:
  • Heapsort hat eine garantierte Laufzeit von \(O(n \log n)\) in allen Fällen.
  • Es ist In-Situ, aber nicht stabil und in der Praxis oft langsamer als Quicksort.
• Bubble Sort:
  • Bubble Sort ist ineffizient für große Arrays mit einer Zeitkomplexität von \(O(n^2)\) im durchschnittlichen und schlechtesten Fall.
  • Für ein Array mit 1000 Elementen ist es daher nicht geeignet.

Zusammengefasst würde ich Quicksort wählen, da es eine ausgezeichnete Balance zwischen Zeitkomplexität und Speicherbedarf bietet und in der Praxis für große Arrays sehr effizient ist.

Wahl der Suchmethode

Nach dem Sortieren des Arrays ist die Wahl der Suchmethode klar:

• Binäre Suche:
  • Die binäre Suche hat eine Laufzeit von \(O(\log n)\), was sie viel effizienter macht als die lineare Suche.
  • Sie ist ideal für wiederholte Suchoperationen in großen, sortierten Arrays.
• Lineare Suche:
  • Die lineare Suche hat eine Laufzeit von \(O(n)\) und ist daher für große Arrays weniger effizient.
  • Sie wird nur empfohlen, wenn das Array unsortiert ist oder wenn Suchoperationen sehr selten sind.

Für das sortierte Array würde ich daher die binäre Suche verwenden, um die Effizienz und Geschwindigkeit der Suchoperationen zu maximieren.