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?
