Wdrożyłem algorytm Quicksort, aby ćwiczyć Pythona, oto mój kod:

def sort(array):   
    if len(array) > 1:
        pivot = array[0]
        left = []
        right = []
        equal = []
        for x in array:
            if x < pivot:
                left.append(x)
            elif x == pivot:
                equal.append(x)
            else:
                right.append(x)
        return sort(left)+equal+sort(right)
    return array

Teraz algorytm pracuje w porządku, ale jeśli usunąć listę equal i wykonaj tę pętlę:

    for x in array:
        if x < pivot:
            left.append(x)
        else:
            right.append(x)
    return sort(left) + sort(right)

Dostaję maksymalny błąd głębokości rekurencji, gdy próbuję posortować listę right. Nie dlatego, że ta lista zawiera również równe elementy, przetestowałem go z bardzo małymi listami. Czuję, że będzie to jakiś naprawdę głupi błąd na mojej stronie, ale nie miałem szczęścia w znalezieniu tego do tej pory.

-1
npace 24 listopad 2013, 17:29

2 odpowiedzi

Najlepsza odpowiedź

Może to wyglądać, nie potrzebujesz listy equal, ale jej obecność jest krytyczna. Umieszczając elementy, które idą tam w liście {X1}}, zmuszasz algorytm do przechowywania elementów sort(), które są już posortowane. Dlatego limit rekurencji zostanie przekroczony.

Dodając print "sorting", array na początku funkcji, możesz zobaczyć, co się dzieje:

>>> sort([3,1,2])
('sorting ', [3, 1, 2])
('sorting ', [1, 2])
('sorting ', [])
('sorting ', [1, 2])
('sorting ', [])
('sorting ', [1, 2])
('sorting ', [])
... etc. until crash
3
Tim Pietzcker 24 listopad 2013, 13:43

Pivot zawsze trafia do right jako element ZEROH i zostaje wybrany ponownie po powtórzeniu right. Ponieważ right zawiera również wszystko, co jest równe lub większe, dlatego, że następne połączenie umieści wszystkie obecnych elementów do nowego {x3}}.

Będzie on zawsze zmniejszony do jednego elementu, jeśli obrys jest wyjątkowy największy element na liście - co ostatecznie oznacza, że w każdy inny przypadek niż lista nie ma duplikatów i już być posortowany w porządku malejącym, ty powtarza się w nieskończoność.

Nie musisz mieć listy equal , ale musisz wziąć przynajmniej wybrany obrotek z rekurencji, więc następnym połączeniem chos jest inny. Więc wybierz to w ten sposób:

pivot = array.pop(0)

I dostosuj rekonstrukcję posortowanej listy:

return sort(left) + [pivot] + sort(right)
2
lvc 24 listopad 2013, 14:01