Wybiera element pivot i dzieli tablicę na mniejsze i większe. Średnio O(n log n).
Sortowanie szybkie to jeden z najszybszych sposobów układania liczb. Pomysł jest prosty: wybierasz jedną liczbę jako punkt odniesienia (nazywamy ją pivotem), a potem rozdzielasz resztę na dwie grupy – mniejsze od niej idą na lewo, większe na prawo.
Co dalej? Pivot stoi już wtedy na swoim miejscu, bo wszystko po lewej jest mniejsze, a po prawej większe. Teraz w ten sam sposób układasz osobno lewą grupę i osobno prawą – i tak dalej, aż każda grupa zrobi się jednoelementowa. Wtedy cała tablica jest gotowa.
Od czego zależy szybkość? Najlepiej, gdy pivot dzieli liczby mniej więcej po połowie. Gdy za każdym razem wypada skrajny (np. dla tablicy już ułożonej), grupy wychodzą bardzo nierówne i algorytm zwalnia. Dlatego na pivot zwykle bierze się element środkowy albo losowy.
Na maturze: najważniejsze jest zrozumienie jednego podziału – kto ląduje po lewej, kto po prawej i w którym miejscu zatrzymuje się pivot.
Prześledź krok po kroku, jak algorytm porządkuje tablicę. Porównywane elementy są podświetlone, a te, które trafiły na swoje docelowe miejsce, zmieniają kolor na zielony.
Naciśnij „Krok", aby wykonać jedną operację, albo „Auto", aby uruchomić całą animację.
funkcja sortuj_szybko(T): jeżeli długość(T) ≤ 1: zwróć T // wybieramy pivot - tu element środkowy pivot ← T[długość(T) div 2] mniejsze ← elementy z T mniejsze od pivot rowne ← elementy z T równe pivot wieksze ← elementy z T większe od pivot // rekurencyjnie sortujemy części i sklejamy zwróć sortuj_szybko(mniejsze) + rowne + sortuj_szybko(wieksze)
def sortowanie_szybkie(tablica):
if len(tablica) <= 1:
return tablica
pivot = tablica[len(tablica) // 2]
mniejsze = [x for x in tablica if x < pivot]
rowne = [x for x in tablica if x == pivot]
wieksze = [x for x in tablica if x > pivot]
return sortowanie_szybkie(mniejsze) + rowne + sortowanie_szybkie(wieksze)
# Przykład użycia
dane = [64, 25, 12, 22, 11, 90, 3]
print(sortowanie_szybkie(dane))
# Wynik: [3, 11, 12, 22, 25, 64, 90]#include <iostream>
#include <vector>
using namespace std;
// Podzial Lomuto - pivotem jest ostatni element
int podzial(vector<int>& t, int lewy, int prawy) {
int pivot = t[prawy]; // element odniesienia
int i = lewy - 1; // granica elementow mniejszych od pivota
for (int j = lewy; j < prawy; j++) {
if (t[j] < pivot) { // element mniejszy trafia na lewo od granicy
i++;
swap(t[i], t[j]);
}
}
swap(t[i + 1], t[prawy]); // pivot laduje na swoim docelowym miejscu
return i + 1; // zwracamy pozycje pivota
}
// Sortowanie w miejscu na przedziale [lewy, prawy]
void sortowanie_szybkie(vector<int>& t, int lewy, int prawy) {
if (lewy < prawy) {
int p = podzial(t, lewy, prawy); // pivot jest juz na miejscu
sortowanie_szybkie(t, lewy, p - 1); // sortujemy mniejsze
sortowanie_szybkie(t, p + 1, prawy); // sortujemy wieksze
}
}
int main() {
vector<int> dane = {64, 25, 12, 22, 11, 90, 3};
sortowanie_szybkie(dane, 0, dane.size() - 1);
for (int x : dane) cout << x << " ";
cout << endl;
// Wynik: 3 11 12 22 25 64 90
return 0;
}Nie – to algorytm niestabilny. Przy przestawianiu elementów wokół pivota kolejność elementów o równych wartościach może się zmienić, bo o zamianie decyduje wyłącznie ich położenie względem pivota, a nie ich pierwotna kolejność.
Zależy to od tego, jak równo pivot dzieli tablicę. Przy zrównoważonych podziałach stos wywołań rekurencyjnych sięga głębokości O(log n). Przy skrajnie nierównych podziałach (najgorszy przypadek – patrz sekcja „Złożoność") drzewo rekurencji robi się wysokie i wąskie, a stos może urosnąć aż do O(n).
Bo sortowanie szybkie w wersji działającej w miejscu porządkuje liczby w obrębie jednej tablicy, bez kopiowania danych do tablic pomocniczych – to lepiej wykorzystuje pamięć podręczną procesora i ma mniejsze stałe czasowe niż sortowanie przez scalanie, które musi alokować i scalać osobne tablice na każdym poziomie rekurencji.
Standardowe funkcje sortujące w wielu językach (np. std::sort w C++) opierają się na wariantach sortowania szybkiego. Sam podział wykorzystuje się też samodzielnie w algorytmie Quickselect do szukania k-tego najmniejszego lub największego elementu bez sortowania całej tablicy.
Przy małych tablicach, gdzie narzut wywołań rekurencyjnych przewyższa korzyść z O(n log n), oraz wszędzie tam, gdzie liczy się stabilność albo gwarancja złożoności O(n log n) w każdym przypadku – wtedy lepszym wyborem jest sortowanie przez scalanie.
Policz i wpisz wynik, potem kliknij Sprawdź.
Przy podziale tablicy o 10 elementach robimy porównań z pivotem, a przy tablicy o 100 elementach porównań.
Uzupełnij tabelę (wpisz O(...) dokładnie tak jak w treści zagadnienia):
| Wielkość | Złożoność |
|---|---|
| Średni przypadek | |
| Najgorszy przypadek | |
| Pamięć (wersja w miejscu) |
Najgorszy przypadek O(n²) pojawia się, gdy pivot jest zawsze elementem – na przykład dla tablicy już . Klasyczne sortowanie szybkie stabilne.
O(n²)O(n log n)O(log n)Średni przypadek to O(n log n). Gdy pivot dzieli tablicę na w miarę równe części, powstaje log n poziomów podziału, a na każdym wykonujemy O(n) porównań – stąd O(n log n). Dla losowych danych dzieje się tak niemal zawsze i dlatego sortowanie szybkie jest w praktyce bardzo szybkie.
Najgorszy przypadek to O(n²). Pojawia się, gdy pivot jest skrajnie nietrafiony – zawsze najmniejszy lub największy element. Klasyczny przykład to tablica już posortowana z pivotem branym zawsze na skraju: każdy podział odcina tylko jeden element, więc rekurencja ma głębokość n, co daje dokładnie O(n²). Opisane w „Opisie" strategie doboru pivota (losowy, mediana z trzech) w praktyce eliminują ten przypadek.
Pamięć. Przedstawiona tu implementacja (listy składane, budowanie nowych tablic mniejsze/rowne/wieksze) zużywa O(n) dodatkowej pamięci. Klasyczna wersja działająca w miejscu dzieli elementy wewnątrz jednej tablicy i potrzebuje jedynie O(log n) na stos wywołań – i to ta wartość widnieje wśród złożoności obok.
Do tego hasła nie mamy jeszcze przypisanych pojedynczych zadań. Cały spis zadań maturalnych z tego działu jest tutaj:
Zagadnienia z tego samego obszaru matury – warto je powtórzyć razem: