Ich habe diese Implementierung des Median-of-Medians-Algorithmus in Python geschrieben, aber es scheint nicht das richtige Ergebnis zu liefern, und es scheint mir auch keine lineare Komplexität zu haben.

def select(L):
    if len(L) < 10:
        L.sort()
        return L[int(len(L)/2)]
    S = []
    lIndex = 0
    while lIndex+5 < len(L)-1:
        S.append(L[lIndex:lIndex+5])
        lIndex += 5
    S.append(L[lIndex:])
    Meds = []
    for subList in S:
        print(subList)
    Meds.append(select(subList))
    L2 = select(Meds)
    L1 = L3 = []
    for i in L:
        if i < L2:
            L1.append(i)
        if i > L2:
            L3.append(i)
    if len(L) < len(L1):
        return select(L1)
    elif len(L) > len(L1) + 1:
        return select(L3)
    else:
        return L2

Die Funktion heißt so:

L = list(range(100))
shuffle(L)
print(select(L))

LE: Entschuldigung. GetMed war eine Funktion, die einfach die Liste sortierte und das Element bei len (list) zurückgab. Es sollte dort ausgewählt worden sein. Ich habe es jetzt behoben, aber ich erhalte immer noch die falschen Ausgaben. Was den Einzug betrifft, so funktioniert der Code fehlerfrei und ich sehe nichts falsches daran: - ??

LE2: Ich erwarte 50 (für das aktuelle L), es gibt mir Ausgaben von 30 bis 70, nicht mehr und (noch) nicht weniger.

LE3: Vielen Dank, das hat den Trick gemacht, der jetzt funktioniert. Ich bin allerdings verwirrt, ich versuche einen Vergleich zwischen dieser Methode und der naiven, bei der ich einfach das Array sortiere und die Ergebnisse ausgebe. Nach dem, was ich bisher gelesen habe, sollte die zeitliche Komplexität der Auswahlmethode O (n) sein.Deterministische Selektion. Obwohl ich wahrscheinlich nicht mit den Optimierungs-Python-Entwicklern mithalten kann, habe ich genauere Ergebnisse erwartet, als ich sie erhalten habe. Wenn ich zum Beispiel den Bereich der Liste auf 10000000 ändere, gibt select das Ergebnis in 84.10837116255952 Sekunden aus, während die Methode sort and return verwendet wird tut es in 18.92556029528825. Was sind einige gute Möglichkeiten, um diesen Algorithmus schneller zu machen?