Przewodnik po algorytmie szybkiego sortowania w języku Python
Poznaj algorytm szybkiego sortowania w Pythonie. Naucz się selekcji przestawnej, partycjonowania i rekurencji w tym interaktywnym przykładzie kodowania.
Przegląd
Quicksort to niezwykle szybki i szeroko stosowany algorytm sortowania. Podobnie jak sortowanie przez scalanie, wykorzystuje metodę „dziel i zwyciężaj”. Jednak szybkie sortowanie sortuje elementy „na miejscu”, dzięki czemu pamięć jest wydajna.
Algorytm działa poprzez wybranie elementu obrotowego z listy. Następnie dzieli pozostałe elementy na dwie podtablice: te mniejsze od osi i te większe od osi. Proces ten jest rekurencyjnie stosowany do podtablic.
Chociaż Quicksort ma złożoność w najgorszym przypadku wynoszącą O(n²), jego średni czas działania wynosi O(n log n) i zazwyczaj w praktyce przewyższa sortowanie przez scalanie ze względu na mniejszą liczbę braków w pamięci podręcznej i zerowy narzut związany z tworzeniem tablic tymczasowych.
Dane wyjściowe kodu i wykonania
Zwięzły, rekurencyjny skrypt szybkiego sortowania wykorzystujący wyrażenia listowe w celu zapewnienia wysokiej czytelności.
def quicksort(arr):
if len(arr) <= 1:
return arr
else:
pivot = arr[len(arr) // 2]
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quicksort(left) + middle + quicksort(right)
# Test list
data = [12, 4, 5, 6, 7, 3, 1, 15]
print("Original List:", data)
sorted_data = quicksort(data)
print("Sorted List: ", sorted_data)Original List: [12, 4, 5, 6, 7, 3, 1, 15]
Sorted List: [1, 3, 4, 5, 6, 7, 12, 15]Wdrażanie krok po kroku
- Procedury sortowania systemu, w których ilość pamięci musi być ograniczona do minimum
- Sortowanie ogólnego przeznaczenia w ramach bibliotek języków standardowych
- Nauczanie akademickie mechaniki podziału i rekurencyjnego dziel i zwyciężaj
Często zadawane pytania
Jak możemy uniknąć najgorszej złożoności O(n²) w Quicksort?
Najgorszy przypadek ma miejsce, gdy wybrany oś jest wielokrotnie najmniejszym lub największym elementem. Aby temu zaradzić, programiści stosują strategie takie jak wybieranie losowego obrotu lub wartości „mediany z trzech”.
Czy Quicksort jest stabilny?
Nie, standardowy Quicksort jest niestabilny. Podczas partycjonowania elementy są zamieniane między długimi zakresami, co może zmieniać względną kolejność zduplikowanych elementów.
Powiązane tematy
Dowiedz się, jak zaimplementować sortowanie przez scalanie w Pythonie. Interaktywny przykład strategii sortowania „Dziel i zwyciężaj” krok po kroku.
Algorytmy sortowania w PythoniePoznaj algorytmy sortowania w Pythonie. Wizualizuj sortowanie bąbelkowe i sortowanie przez scalanie natywnie w kontekście IDE przeglądarki.
Algorytm wyszukiwania binarnego w PythoniePrzeszukuj posortowane listy w logarytmicznym czasie O(log n). Uruchom i zrozum wyszukiwanie binarne w Pythonie, w tym logikę krok po kroku, przypadki brzegowe i optymalizacje.