Szybkie sortowanie w Pythonie
W prawdziwym życiu powinniśmy zawsze używać wbudowanego sortowania udostępnianego przez Pythona. Jednak zrozumienie algorytmu quicksort jest pouczające.
Moim celem jest takie rozbicie tematu, aby był on łatwy do zrozumienia i odtworzenia przez czytelnika bez konieczności powracania do materiałów referencyjnych.
Algorytm szybkiego sortowania jest zasadniczo następujący:
- Wybierz obrotowy punkt danych.
- Przenieś wszystkie punkty danych poniżej (poniżej) obrotu do pozycji poniżej osi - przesuń te większe lub równe (powyżej) obrotu do pozycji nad nim.
- Zastosuj algorytm do obszarów powyżej i poniżej osi obrotu
Jeśli dane są rozmieszczone losowo, wybranie pierwszego punktu danych jako osi obrotu jest równoważne z wyborem losowym.
Czytelny przykład:
Najpierw spójrzmy na czytelny przykład, w którym zastosowano komentarze i nazwy zmiennych, aby wskazać wartości pośrednie:
def quicksort(xs):
"""Given indexable and slicable iterable, return a sorted list"""
if xs:
pivot = xs[0]
below = [i for i in xs[1:] if i < pivot]
above = [i for i in xs[1:] if i >= pivot]
return quicksort(below) + [pivot] + quicksort(above)
else:
return xs
Aby powtórzyć pokazany tutaj algorytm i kod - przenosimy wartości powyżej osi w prawo, a wartości poniżej osi w lewo, a następnie przekazujemy te partycje do tej samej funkcji w celu dalszego sortowania.
Grał w golfa:
Można grać w golfa do 88 znaków:
q=lambda x:x and q([i for i in x[1:]if i<=x[0]])+[x[0]]+q([i for i in x[1:]if i>x[0]])
Aby zobaczyć, jak to osiągnąć, weźmy najpierw nasz czytelny przykład, usuń komentarze i dokumenty, a następnie znajdź punkt zwrotny w miejscu:
def quicksort(xs):
if xs:
below = [i for i in xs[1:] if i < xs[0]]
above = [i for i in xs[1:] if i >= xs[0]]
return quicksort(below) + [xs[0]] + quicksort(above)
else:
return xs
Teraz znajdź poniżej i powyżej, na miejscu:
def quicksort(xs):
if xs:
return (quicksort([i for i in xs[1:] if i < xs[0]] )
+ [xs[0]]
+ quicksort([i for i in xs[1:] if i >= xs[0]]))
else:
return xs
Teraz, wiedząc, że and
zwraca poprzedni element, jeśli jest fałszywy, w przeciwnym razie, jeśli jest prawdziwy, ocenia i zwraca następujący element, mamy:
def quicksort(xs):
return xs and (quicksort([i for i in xs[1:] if i < xs[0]] )
+ [xs[0]]
+ quicksort([i for i in xs[1:] if i >= xs[0]]))
Ponieważ lambdy zwracają pojedyncze wyrażenie, a my uprościliśmy się do jednego wyrażenia (nawet jeśli staje się ono bardziej nieczytelne), możemy teraz użyć lambdy:
quicksort = lambda xs: (quicksort([i for i in xs[1:] if i < xs[0]] )
+ [xs[0]]
+ quicksort([i for i in xs[1:] if i >= xs[0]]))
Aby sprowadzić się do naszego przykładu, skróć nazwy funkcji i zmiennych do jednej litery oraz wyeliminuj białe znaki, które nie są wymagane.
q=lambda x:x and q([i for i in x[1:]if i<=x[0]])+[x[0]]+q([i for i in x[1:]if i>x[0]])
Zauważ, że ta lambda, podobnie jak większość golfistów kodowych, jest raczej złym stylem.
Lokalne szybkie sortowanie przy użyciu schematu partycjonowania Hoare
Wcześniejsze wdrożenie tworzy wiele niepotrzebnych dodatkowych list. Jeśli możemy to zrobić na miejscu, unikniemy marnowania miejsca.
Poniższa implementacja używa schematu partycjonowania Hoare, o którym możesz przeczytać więcej na Wikipedii (ale najwyraźniej usunęliśmy do 4 zbędnych obliczeń na partition()
wywołanie, używając semantyki while-loop zamiast do-while i przenosząc zwężające kroki na koniec zewnętrzna pętla while.).
def quicksort(a_list):
"""Hoare partition scheme, see https://en.wikipedia.org/wiki/Quicksort"""
def _quicksort(a_list, low, high):
if low < high:
p = partition(a_list, low, high)
_quicksort(a_list, low, p)
_quicksort(a_list, p+1, high)
def partition(a_list, low, high):
pivot = a_list[low]
while True:
while a_list[low] < pivot:
low += 1
while a_list[high] > pivot:
high -= 1
if low >= high:
return high
a_list[low], a_list[high] = a_list[high], a_list[low]
low += 1
high -= 1
_quicksort(a_list, 0, len(a_list)-1)
return a_list
Nie jestem pewien, czy przetestowałem go wystarczająco dokładnie:
def main():
assert quicksort([1]) == [1]
assert quicksort([1,2]) == [1,2]
assert quicksort([1,2,3]) == [1,2,3]
assert quicksort([1,2,3,4]) == [1,2,3,4]
assert quicksort([2,1,3,4]) == [1,2,3,4]
assert quicksort([1,3,2,4]) == [1,2,3,4]
assert quicksort([1,2,4,3]) == [1,2,3,4]
assert quicksort([2,1,1,1]) == [1,1,1,2]
assert quicksort([1,2,1,1]) == [1,1,1,2]
assert quicksort([1,1,2,1]) == [1,1,1,2]
assert quicksort([1,1,1,2]) == [1,1,1,2]
Wniosek
Ten algorytm jest często nauczany na kursach informatycznych i proszony o udział w rozmowach kwalifikacyjnych. Pomaga nam myśleć o rekurencji oraz dziel i rządź.
Szybkie sortowanie nie jest zbyt praktyczne w Pythonie, ponieważ nasz wbudowany algorytm sortowania czasu jest dość wydajny i mamy ograniczenia rekursji. Spodziewalibyśmy się sortowania list na miejscu za pomocą list.sort
lub tworzenia nowych posortowanych list za pomocą sorted
- obie przyjmują argument key
i reverse
.
my_list = list1 + list2 + ...
. Lub rozpakuj listy do nowej listymy_list = [*list1, *list2]