Quick Sort i wybór pivota
Zbudują Państwo Quick Sort z wykorzystaniem schematów podziału Lomuto i Hoare’a, omówią pesymistyczną złożoność O(n²) oraz sposób, w jaki losowy wybór pivota ją ogranicza.
Quick Sort i wybór pivota to bezpłatna lekcja DSA Interview Prep na CoddyKit. To lekcja 3 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej DSA Interview Prep, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs DSA Interview Prep zawiera 4 lekcji w sumie.
Quicksort: dziel i zwyciężaj w miejscu
Quicksort jest w praktyce najczęściej używanym algorytmem sortowania. W przeciwieństwie do sortowania przez scalanie sortuje w miejscu, bez przydzielania dodatkowych tablic. Podstawowa idea polega na wybraniu elementu pivot, podzieleniu tablicy tak, aby wszystkie elementy mniejsze od pivota znalazły się przed nim, a wszystkie większe — za nim, a następnie rekurencyjnym posortowaniu każdej części. Etap partycjonowania zajmuje O(n), a przy dobrym pivocie głębokość rekurencji wynosi O(log n).
def quick_sort(arr, lo=0, hi=None):
if hi is None: hi = len(arr) - 1
if lo < hi:
pivot_idx = partition(arr, lo, hi)
quick_sort(arr, lo, pivot_idx - 1) # sort left
quick_sort(arr, pivot_idx + 1, hi) # sort right
def partition(arr, lo, hi):
pivot = arr[hi] # Lomuto: choose last element as pivot
i = lo - 1
for j in range(lo, hi):
if arr[j] <= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i+1], arr[hi] = arr[hi], arr[i+1]
return i + 1
arr = [3, 6, 8, 10, 1, 2, 1]
quick_sort(arr)
print(arr) # [1, 1, 2, 3, 6, 8, 10]Schemat partycjonowania Lomuto
Partycjonowanie Lomuto jako pivota używa ostatniego elementu. Wolny wskaźnik i wyznacza granicę obszaru „mniejszych od pivota”, a szybki wskaźnik j przesuwa się do przodu. Gdy arr[j] <= pivot, zwiększamy i i zamieniamy miejscami arr[i] oraz arr[j], rozszerzając obszar małych elementów. Po zakończeniu skanowania umieszczamy pivota w pozycji i+1, zamieniając go miejscami z arr[hi]. Schemat jest prosty w implementacji, ale wykonuje 3× więcej zamian niż schemat Hoare’a.
def lomuto_partition_traced(arr, lo, hi):
pivot = arr[hi]
i = lo - 1
print(f'Pivot: {pivot}, array: {arr[lo:hi+1]}')
for j in range(lo, hi):
if arr[j] <= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i+1], arr[hi] = arr[hi], arr[i+1]
print(f'After partition: {arr[lo:hi+1]}')
return i + 1
arr = [3, 1, 4, 1, 5, 9, 2, 6]
lomuto_partition_traced(arr, 0, len(arr)-1)Schemat partycjonowania Hoare’a
Partycjonowanie Hoare’a wykorzystuje dwa wskaźniki rozpoczynające pracę na obu końcach tablicy i przesuwające się do środka, aż się przetną. Wybiera ono pivota (zwykle pierwszy element), a następnie przesuwa elementy mniejsze od pivota na lewo, a większe na prawo. Schemat Hoare’a wykonuje 3× mniej zamian niż Lomuto i lepiej radzi sobie z równymi elementami, ale po partycjonowaniu pivot nie znajduje się jeszcze na swojej ostatecznej pozycji — dlatego konieczne są nieco inne wywołania rekurencyjne.
def hoare_partition(arr, lo, hi):
pivot = arr[lo] # first element as pivot
i, j = lo - 1, hi + 1
while True:
i += 1
while arr[i] < pivot: i += 1
j -= 1
while arr[j] > pivot: j -= 1
if i >= j: return j
arr[i], arr[j] = arr[j], arr[i]
def quick_sort_hoare(arr, lo=0, hi=None):
if hi is None: hi = len(arr) - 1
if lo < hi:
p = hoare_partition(arr, lo, hi)
quick_sort_hoare(arr, lo, p) # note: p not p-1
quick_sort_hoare(arr, p+1, hi)
arr = [3, 6, 8, 10, 1, 2, 1]
quick_sort_hoare(arr)
print(arr) # [1, 1, 2, 3, 6, 8, 10]Najgorszy przypadek O(n²): już posortowane dane wejściowe
Najgorszy przypadek quicksorta występuje, gdy pivot jest stale najmniejszym lub największym elementem partycji. Przy użyciu ostatniego elementu jako pivota w schemacie Lomuto i już posortowanej tablicy partycjonowanie zawsze umieszcza 0 elementów po lewej i n-1 po prawej stronie: drzewo rekurencji degeneruje się do łańcucha o głębokości n, co daje O(n²) porównań. Dlatego wybór pivota ma kluczowe znaczenie, a implementacje produkcyjne losują pivota.
import sys
sys.setrecursionlimit(5000)
def quick_sort_naive(arr, lo=0, hi=None):
if hi is None: hi = len(arr) - 1
comparisons = [0]
def _qs(lo, hi):
if lo >= hi: return
pivot = arr[hi] # last element pivot
i = lo - 1
for j in range(lo, hi):
comparisons[0] += 1
if arr[j] <= pivot:
i += 1; arr[i], arr[j] = arr[j], arr[i]
arr[i+1], arr[hi] = arr[hi], arr[i+1]
p = i + 1
_qs(lo, p-1); _qs(p+1, hi)
_qs(lo, hi)
return comparisons[0]
import math
n = 100
sorted_arr = list(range(n))
ops = quick_sort_naive(sorted_arr)
print(f'n={n}, ops={ops}, n^2={n**2}') # ops close to n*(n-1)/2Losowy pivot: oczekiwane O(n log n)
Wybierając pivota równomiernie losowo (przed partycjonowaniem zamieniając losowy element z arr[hi]), zmniejszamy wykładniczo prawdopodobieństwo konsekwentnego wybierania złych pivotów. Oczekiwana liczba porównań wynosi 2n ln(n) ≈ 1.39 n log₂(n), co daje oczekiwany czas O(n log n) z przytłaczającym prawdopodobieństwem. Dlatego w praktyce stosuje się losowy quicksort — pozwala uniknąć patologicznych najgorszych przypadków, które przeciwnik mógłby skonstruować dla strategii ze stałym pivotem.
import random
def quick_sort_random(arr, lo=0, hi=None):
if hi is None: hi = len(arr) - 1
if lo < hi:
# Randomise pivot
rand_i = random.randint(lo, hi)
arr[rand_i], arr[hi] = arr[hi], arr[rand_i]
# Lomuto partition with last element as pivot
pivot = arr[hi]
i = lo - 1
for j in range(lo, hi):
if arr[j] <= pivot:
i += 1; arr[i], arr[j] = arr[j], arr[i]
arr[i+1], arr[hi] = arr[hi], arr[i+1]
p = i + 1
quick_sort_random(arr, lo, p - 1)
quick_sort_random(arr, p + 1, hi)
arr = list(range(100, 0, -1)) # worst case for naive
quick_sort_random(arr)
print(arr[:10]) # [1,2,3,4,5,6,7,8,9,10]Pivot jako mediana z trzech
Inna strategia wyboru pivota polega na wybraniu mediany pierwszego, środkowego i ostatniego elementu. Pozwala to uniknąć najgorszego działania dla danych posortowanych lub posortowanych odwrotnie (najczęstszych danych adversarialnych), a jednocześnie nie wymaga generowania liczb losowych. Wiele implementacji produkcyjnych używa mediany z trzech lub ninthera (mediany trzech median) dla dużych tablic, a dla małych podtablic, poniżej progu około 10 elementów, przełącza się na sortowanie przez wstawianie.
def median_of_three(arr, lo, hi):
mid = (lo + hi) // 2
# Sort lo, mid, hi values in place
if arr[lo] > arr[mid]: arr[lo], arr[mid] = arr[mid], arr[lo]
if arr[lo] > arr[hi]: arr[lo], arr[hi] = arr[hi], arr[lo]
if arr[mid] > arr[hi]: arr[mid], arr[hi] = arr[hi], arr[mid]
# Median is now at arr[mid]; swap to arr[hi-1] as pivot
arr[mid], arr[hi] = arr[hi], arr[mid]
return arr[hi] # pivot value
arr = [3, 9, 1]
print(median_of_three(arr, 0, 2), arr) # 3, [1,3,9] (sorted)Flaga holenderska: partycjonowanie trójstronne
Standardowe partycjonowanie umieszcza elementy mniejsze od pivota po lewej, a większe po prawej, ale elementy równe pivotowi pozostają rozproszone. Partycjonowanie trójstronne (flaga holenderska) tworzy trzy regiony: <pivot, ==pivot, >pivot. Ma to kluczowe znaczenie dla tablic zawierających wiele duplikatów — w takich przypadkach standardowy quicksort obniża się do O(n²), podczas gdy quicksort trójstronny działa w czasie O(n) dla danych, w których wszystkie wartości są takie same.
def three_way_partition(arr, lo, hi):
pivot = arr[lo]
lt = lo # arr[lo..lt-1] < pivot
gt = hi # arr[gt+1..hi] > pivot
i = lo # current
while i <= gt:
if arr[i] < pivot:
arr[lt], arr[i] = arr[i], arr[lt]
lt += 1; i += 1
elif arr[i] > pivot:
arr[i], arr[gt] = arr[gt], arr[i]
gt -= 1 # don't advance i
else:
i += 1
return lt, gt # pivot occupies arr[lt..gt]
arr = [3, 1, 4, 1, 5, 9, 2, 6, 3, 3]
lt, gt = three_way_partition(arr, 0, len(arr)-1)
print(arr, '| pivot region:', lt, 'to', gt)Quickselect: k-ty najmniejszy element w O(n)
Quickselect wykorzystuje etap partycjonowania quicksorta do znalezienia k-tego najmniejszego elementu w średnim czasie O(n), bez pełnego sortowania. Po partycjonowaniu pivot znajduje się na swojej ostatecznej pozycji p. Jeśli p == k, zwracamy arr[p]. Jeśli k < p, wykonujemy rekurencję dla lewej partycji; jeśli k > p, dla prawej. Średnio każda rekurencja zmniejsza problem o połowę: O(n) + O(n/2) + O(n/4) + ... = O(2n) = O(n).
import random
def quickselect(nums, k):
'''Find kth smallest (0-indexed) in O(n) average.'''
def _select(lo, hi):
if lo == hi: return nums[lo]
rand_i = random.randint(lo, hi)
nums[rand_i], nums[hi] = nums[hi], nums[rand_i]
pivot = nums[hi]
i = lo - 1
for j in range(lo, hi):
if nums[j] <= pivot:
i += 1; nums[i], nums[j] = nums[j], nums[i]
p = i + 1
nums[p], nums[hi] = nums[hi], nums[p]
if p == k: return nums[p]
elif k < p: return _select(lo, p - 1)
else: return _select(p + 1, hi)
return _select(0, len(nums) - 1)
print(quickselect([3,2,1,5,6,4], 1)) # 2 (2nd smallest)Złożoność pamięciowa quicksorta
Quicksort nazywa się algorytmem działającym „w miejscu”, ale rekurencja wykorzystuje średnio O(log n) pamięci stosu (po jednej ramce na poziom drzewa rekurencji). W najgorszym przypadku głębokość stosu wynosi O(n). Aby zagwarantować O(log n) pamięci stosu w najgorszym przypadku, należy zawsze wykonywać rekurencję najpierw dla mniejszej partycji i stosować optymalizację wywołań ogonowych dla większej partycji. Limit rekurencji Pythona sprawia, że bardzo głębokie rekurencje quicksorta są ryzykowne — warto wspomnieć o tym podczas rozmów kwalifikacyjnych.
def quick_sort_optimised(arr, lo=0, hi=None):
if hi is None: hi = len(arr) - 1
while lo < hi:
p = lomuto_partition_qs(arr, lo, hi)
# Recurse on smaller partition; iterate on larger
if p - lo < hi - p:
quick_sort_optimised(arr, lo, p - 1)
lo = p + 1 # tail-call elimination
else:
quick_sort_optimised(arr, p + 1, hi)
hi = p - 1
def lomuto_partition_qs(arr, lo, hi):
pivot = arr[hi]; i = lo - 1
for j in range(lo, hi):
if arr[j] <= pivot: i += 1; arr[i], arr[j] = arr[j], arr[i]
arr[i+1], arr[hi] = arr[hi], arr[i+1]
return i + 1Porównanie algorytmów sortowania
Podsumujmy wiedzę:
- Quicksort: oczekiwane O(n log n), O(n²) w najgorszym przypadku, O(log n) pamięci, niestabilny, w praktyce najszybszy dla losowych danych
- Sortowanie przez scalanie: gwarantowane O(n log n), O(n) pamięci, stabilne, najlepsze dla list wiązanych i sortowania zewnętrznego
- Heapsort: gwarantowane O(n log n), O(1) pamięci, niestabilny, w praktyce wolniejszy z powodu chybień pamięci podręcznej
- Sortowanie przez wstawianie: O(n) w najlepszym przypadku, idealne dla małych n lub danych prawie posortowanych
# Python's sorted() uses Timsort:
# - Hybrid: merge sort for large runs, insertion sort for small (< 64 elements)
# - Stable, O(n log n) worst case
# - O(n) best case for sorted/reverse-sorted/nearly-sorted
# - O(n) extra space
import random
arr = random.sample(range(10000), 1000)
sorted_arr = sorted(arr) # Timsort
print(sorted_arr[:5], '...') # first 5 elementsIntrosort: połączenie wszystkich trzech algorytmów
Introsort (używany w C++ STL std::sort) łączy quicksort, heapsort i sortowanie przez wstawianie: rozpoczyna od losowego quicksorta; jeśli głębokość rekurencji przekroczy 2 log n (co wskazuje na sekwencję złych pivotów), przełącza się na heapsort, aby zagwarantować O(n log n); dla podtablic mniejszych niż 16 elementów używa sortowania przez wstawianie. Daje to O(n log n) w najgorszym przypadku, szybkość quicksorta w średnim przypadku oraz wydajność sortowania przez wstawianie dla małych podtablic.
# Introsort hybrid (simplified)
def introsort(arr, depth_limit=None):
if depth_limit is None:
import math
depth_limit = 2 * int(math.log2(len(arr) + 1)) if arr else 0
if len(arr) <= 16:
# insertion sort for small arrays
for i in range(1, len(arr)):
key = arr[i]; j = i - 1
while j >= 0 and arr[j] > key:
arr[j+1] = arr[j]; j -= 1
arr[j+1] = key
return arr
if depth_limit == 0:
arr.sort() # fall back to heapsort equivalent
return arr
# Otherwise quick sort
pivot = arr[-1]
small = [x for x in arr[:-1] if x <= pivot]
large = [x for x in arr[:-1] if x > pivot]
return introsort(small, depth_limit-1) + [pivot] + introsort(large, depth_limit-1)
print(introsort([5,3,8,1,9,2,7]))Szybki test
Sprawdź swoją wiedzę z koncepcji kursu Data Structures & Algorithms — Coding Interview Prep omówionych w tej lekcji.
Podsumowanie lekcji
W tej lekcji nauczył(a) się Pan/Pani, że: quicksort dzieli tablicę wokół pivota w miejscu i wykonuje rekurencję dla obu stron, osiągając oczekiwany czas O(n log n) przy O(log n) pamięci stosu — w praktyce jest szybszy od sortowania przez scalanie dla losowych danych, najgorszy przypadek O(n²) występuje dla posortowanych danych przy stałym pivocie i można go uniknąć dzięki losowemu wyborowi pivota lub medianie z trzech, a także że partycjonowanie trójstronne efektywnie obsługuje zduplikowane elementy, a quickselect rozszerza ideę partycjonowania, aby znajdować k-ty najmniejszy element w średnim czasie O(n), bez pełnego sortowania. Następnie omówimy sortowania nieporównawcze oraz wbudowane sortowanie Pythona.
Często zadawane pytania
Czy lekcja „Quick Sort i wybór pivota” jest bezpłatna?
Tak — pełny tekst „Quick Sort i wybór pivota” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu DSA Interview Prep, przejdź na CoddyKit PRO. Kurs DSA Interview Prep zawiera 4 lekcji w sumie.
Co nauczysz się w „Quick Sort i wybór pivota”?
Zbudują Państwo Quick Sort z wykorzystaniem schematów podziału Lomuto i Hoare’a, omówią pesymistyczną złożoność O(n²) oraz sposób, w jaki losowy wybór pivota ją ogranicza. Ćwiczysz DSA Interview Prep z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.
Czy potrzebuję doświadczenia, aby zacząć DSA Interview Prep?
Nie wymagamy żadnego doświadczenia. DSA Interview Prep w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 3 z 4.
Ile czasu zajmuje lekcja „Quick Sort i wybór pivota”?
Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.
Czy mogę pisać i uruchamiać kod w tej lekcji DSA Interview Prep?
Tak. Każda lekcja DSA Interview Prep zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.
Wszystkie lekcje w tym kursie
- Sortowanie bąbelkowe i przez wstawianie
- Sortowanie przez scalanie: podziel, posortuj, scal
- Quick Sort i wybór pivota
- Sortowania nieporównawcze i sort() w Pythonie