QuickSort i Counting Sort

QuickSort również dzieli problem na mniejsze, ale inaczej niż MergeSort: wybiera pivot (element rozdzielający), a następnie partycjonuje tablicę tak, by elementy mniejsze od pivota były po lewej, a większe po prawej. Sam pivot trafia na docelową pozycję, a algorytm rekurencyjnie sortuje obie strony.

def quick_sort(tab): if len(tab) <= 1: return tab pivot = tab[len(tab) // 2] mniejsze = [x for x in tab if x < pivot] rowne = [x for x in tab if x == pivot] wieksze = [x for x in tab if x > pivot] return quick_sort(mniejsze) + rowne + quick_sort(wieksze)

Najgorszy przypadek

Jeśli pivot zawsze trafia na najmniejszy lub największy element (np. przy już posortowanej tablicy i wyborze pierwszego elementu jako pivota), podział jest bardzo nierówny i złożoność spada do O(n²). Dlatego w praktyce pivot wybiera się losowo lub jako medianę z kilku próbek.

2. Counting Sort — sortowanie liniowe

Przypadek	Złożoność	Kiedy występuje
Średni	O(n log n)	Pivot dzieli tablicę w miarę równo
Najgorszy	O(n²)	Pivot zawsze skrajny (źle posortowane/dobrane dane)

Jeśli wiemy, że sortowane liczby mieszczą się w ograniczonym, niewielkim zakresie (np. oceny 1–6, wiek 0–120), można posortować je w czasie liniowym O(n + k), gdzie k to rozpiętość zakresu — bez żadnych porównań elementów między sobą!

def counting_sort(tab, maks): licznik = [0] * (maks + 1) for x in tab: licznik[x] += 1 wynik = [] for wartosc in range(maks + 1): wynik.extend([wartosc] * licznik[wartosc]) return wynik # counting_sort([4, 2, 2, 8, 3, 3, 1], 8)

Kiedy Counting Sort ma sens?

Tylko gdy zakres wartości k jest mały w porównaniu z n. Dla k rzędu milionów (np. sortowanie dowolnych liczb całkowitych 32-bitowych) tablica pomocnicza byłaby zbyt duża — wtedy lepiej użyć MergeSort/QuickSort.

3. Ćwiczenia praktyczne

Ćwiczenie 1 — QuickSort in-place

Zaimplementowana wyżej wersja QuickSort tworzy nowe listy (mniejsze/rowne/wieksze), co zużywa dodatkową pamięć. Zbadaj (w dokumentacji lub eksperymentalnie), na czym polega wersja "in-place" z zamianą elementów miejscami wewnątrz oryginalnej tablicy — jaka jest jej przewaga?

Ćwiczenie 2 — posortuj oceny klasy

Mając listę ocen 30 uczniów (wartości 1–6), posortuj ją algorytmem Counting Sort i policz średnią arytmetyczną. Porównaj czas wykonania z wbudowaną funkcją sorted() dla dużej (100 000-elementowej) listy ocen.

Sprawdź wiedzę

1. Jaka jest średnia złożoność czasowa QuickSort?

O(n log n) O(n²) O(n)

2. Kiedy QuickSort osiąga najgorszy przypadek O(n²)?

Gdy pivot zawsze dzieli tablicę równo Gdy pivot zawsze trafia na skrajny element Nigdy — QuickSort zawsze działa w O(n log n)

3. Counting Sort osiąga złożoność liniową, ponieważ:

Używa rekurencji Nie porównuje elementów między sobą, tylko liczy wystąpienia Działa tylko na małych tablicach

1. QuickSort — idea