Arrays und Datentypen: Algorithmus zum verschieben und entfernen des größten Elements

Question

Frage:

Gegeben sei ein Array A, welches n paarweise verschiedene reelle Zahlen A[0], A[1], · · · , A[n −
1] enthält. Das größte Element des Arrays soll gefunden und aus dem Array entfernt und die
nachfolgende Einträge um eine Position nach vorne verschoben werden. Der zugehörige Index des
größten Elements (d.h. die Position des Elements in dem Array) ist nicht vorher bekannt.

a) Schreiben Sie einen Algorithmus (als Pseudocode), der das Array A, und die Anzahl n der
Elemente in A als Eingabe erhält und die oben angeführten Operationen beschreibt. Der Algorithmus soll Ihnen das gekürzte Array und die Länge des neuen Arrays zurückgeben.

b) Wie viele elementare Operationen (Vergleiche, Zuweisungen, Zugriffe auf Array-Elemente und
Rechenoperationen) benötigt Ihr Algorithmus maximal?

c) Angenommen, n wäre ungerade: Wie könnten Sie Ihren Algorithmus nutzen, um den Median,
also den zentralen Wert, des Arrays zu bestimmen?

Answer 1

Antwort mit KI erzeugt

Teil a: Algorithmus

Wir entwickeln einen Algorithmus in Pseudocode, der das größte Element aus dem Array entfernt und die Länge des Arrays aktualisiert.

plaintext
Algorithmus entferneGroesstesElement(A, n):
1. Start:
2.    maxSize <- A[0]
3.    maxIndex <- 0
4.    for i <- 1 to n-1 do
5.        if A[i] > maxSize then
6.            maxSize <- A[i]
7.            maxIndex <- i
8.    end for
9.    for j <- maxIndex to n-2 do
10.       A[j] <- A[j + 1]
11.   end for
12.   n <- n - 1
13.   return A, n

Der Algorithmus sucht zunächst durch den Vergleich aller Elemente das größte Element und dessen Index im Array. Anschließend verschiebt er die darauf folgenden Elemente um eine Position nach vorne, wodurch das größte Element überschrieben wird. Zuletzt verringert er die Gesamtzahl der Elemente (\(n\)) um eins, um das Entfernen des größten Elements zu reflektieren.

Teil b: Elementare Operationen

Die Anzahl der elementaren Operationen kann wie folgt abgeschätzt werden:

- Die ersten Zuweisungen (Zeile 2 und 3) sind jeweils eine Operation, insgesamt also 2.
- Der for-Loop von Zeile 4 bis 8 führt \(n-1\) Iterationen durch, wobei jede Iteration eine Vergleichsoperation und im schlechtesten Fall eine Zuweisungsoperation für \(maxSize\) und \(maxIndex\) durchführt. Das ergibt maximal \(3(n-1)\) Operationen.
- Der zweite for-Loop von Zeile 9 bis 11 führt im schlimmsten Fall \(n-1\) Iterationen durch, mit je einer Zuweisungsoperation, was zu \(n-1\) Operationen führt.
- Die Operation in Zeile 12 ist eine weitere Zuweisung.

Im schlechtesten Fall ergibt sich somit eine maximale Anzahl elementarer Operationen von \(2 + 3(n-1) + (n-1) + 1 = 4n - 2\).

Teil c: Median bestimmen

Um den Median eines Arrays zu bestimmen, wenn \(n\) ungerade ist, könnte der Algorithmus entferneGroesstesElement genutzt werden, um das Array so oft zu verkürzen, bis es genau das Mittlerelement enthält, das dann den Median darstellen würde. Der Median ist das Element, das sich an der Position \(\frac{n}{2}\) (nach unten gerundet, da Arrays in der Informatik in der Regel bei 0 beginnen) in einem sortierten Array befindet.

Für ein ungerades \(n\), müssten Sie daher das größte Element \(\frac{n - 1}{2}\) Mal entfernen, um den Median zu extrahieren. Jedes Mal, wenn das größte Element entfernt wird, rückt das Array näher an eine sortierte Reihenfolge heran, da das jeweils größte verbleibende Element entfernt wird. Nach \(\frac{n - 1}{2}\) Iterationen ist das größte der verbleibenden Elemente der Median des ursprünglichen Arrays.

Beachtet werden muss jedoch, dass das direkte Anwenden dieses Verfahrens das Originalarray verändert und nicht effizient für die Medianberechnung ist, insbesondere wenn das Array groß ist oder wiederholt darauf zugegriffen werden muss. In der Praxis ist es oft besser, effizientere Methoden zur Bestimmung des Medians, wie Medians-of-Medians oder Quickselect, zu verwenden.