Napisałem tę implementację mediany algorytmu median w Pythonie, ale wydaje się, że nie daje prawidłowego wyniku, a także nie wydaje mi się liniową złożonością, jakimkolwiek pomysłem, gdzie poszedłem poza ścieżkę?

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

Funkcja nazywa się tak:

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

LE: Przepraszam. GetMed to funkcja, która po prostu posortowała listę i zwróciła element na len (lista), powinna być tam zaznaczona, naprawiłem ją teraz, ale nadal otrzymuję nieprawidłowe wyniki. Jeśli chodzi o wcięcia, kod działa bezbłędnie i nie widzę w tym nic złego: - ??

LE2: Spodziewam się 50 (dla obecnego L), daje mi to wyniki od 30 do 70, nie więcej (jeszcze)

LE3: Dziękuję bardzo, że to działa teraz. Jestem jednak zdezorientowany, próbuję dokonać porównania między tą metodą a tą naiwną, gdzie po prostu sortuję tablicę i wypisuję wyniki. Teraz, z tego, co przeczytałem do tej pory, złożoność czasowa wybranej metody powinna wynosić O (n)Wybór deterministyczny. Chociaż prawdopodobnie nie mogłem konkurować z programistami optymalizującymi Pythona, spodziewałem się bliższych wyników niż ja, na przykład, jeśli zmienię zakres listy na 10000000, wybierz wynik, uzyskując wynik 84.10837116255952 sekundy podczas metody sortowania i powrotu robi to w 18.92556029528825. Jakie są dobre sposoby na przyspieszenie tego algorytmu?