Bei dem Select Algorithmus wird das Array erstmal in Gruppen von x Elementen (am besten eine ungerade Anzahl) aufgeteilt meist 5. Hier also:
Array Länge n = 10, Anzahl der Teilarrays k= n // 5 = 2
\( T_{0} \) = [8,0,1,4,6], \( T_{1} \) = [9,3,2,7,5]
von jedem Teilarray wird dann der Median gesucht (also Array sortieren und Median finden)
Das Array der Mediane m ist dann: [4,5].
Durch den Rekursiven Aufruf des Algorithmus kann man dann den Median der Mediane finden (normalerweise 4,5 weil gerade Anzahl von Elementen, hier aber das kleinere Element also 4). Hierbei entstehen die Arrays K=[], M=[4] und G=[5] (kleiner/gleich/größer als der Median)
und auf das ganze Array betrachtet nach dem rekursiven Aufruf:
K=[0,1,3,2], M=[4], G=[8,6,9,7,5] (sortiert wird hier nicht, um die Laufzeit zu verkürzen)
Da du mit l=5 die 5. Stelle des sortieren Arrays suchst, folgen weitere rekursive Aufrufe :
- Falls die Anzahl von K-Elementen ≥ l, führe Select(K, l) aus
- sonst, falls Anzahl von K-Elementen + M-Elementen ≥ l, gib den Median aus;
- sonst führe Select(G, l − Anzahl K-Elemente − Anzahl-M-Elemente) aus.
Am Ende solltest du die Ausgabe haben, dass das 5. Element (in dem sortierten Array) = 4 ist (wegen 0,1,2,3,4)
