Wybiera element pivot i dzieli tablicę na mniejsze i większe. Średnio O(n log n).
Sortowanie szybkie to algorytm oparty na strategii "dziel i zwyciężaj". W praktyce jest jednym z najszybszych algorytmów sortowania dla losowych danych.
Krok 1 – wybór pivota: wybieramy element odniesienia. Może to być element pierwszy, środkowy, ostatni lub losowy. Wybór wpływa na wydajność dla różnych danych wejściowych.
Krok 2 – podział (partition): dzielimy tablicę na trzy części: elementy mniejsze od pivota, równe pivotowi i większe od pivota.
Krok 3 – rekurencja: rekurencyjnie sortujemy część z mniejszymi i większymi elementami. Środkowa (równe pivotowi) jest już na właściwym miejscu.
Dobór pivota: od trafności pivota zależy wydajność algorytmu (szczegóły w sekcji „Złożoność"). Aby uniknąć niezrównoważonych podziałów, stosuje się sprytniejsze strategie. Losowy pivot – losujemy indeks przed podziałem, przez co przeciwnikowi trudno jest z góry przygotować dane wymuszające najgorszy przypadek (dla dowolnego wejścia zły podział staje się bardzo mało prawdopodobny). Mediana z trzech – bierzemy pierwszy, środkowy i ostatni element tablicy, a jako pivot wybieramy medianę tej trójki; dzięki temu na danych posortowanych czy odwrotnie posortowanych pivot nie jest już skrajny i podział wychodzi zrównoważony. Obie strategie w praktyce eliminują przypadek O(n²).
Stabilność: sortowanie szybkie jest zazwyczaj niestabilne – przy przestawianiu elementów wokół pivota względna kolejność elementów o równych wartościach może się zmienić. Jeśli zależy nam na zachowaniu pierwotnej kolejności równych elementów, lepiej sięgnąć po sortowanie stabilne, np. przez scalanie.
Porównanie z sortowaniem przez scalanie: w quicksorcie cała praca dzieje się w podziale – to partycjonowanie porównuje elementy z pivotem i rozdziela je na mniejsze i większe. Łączenie wyników jest za to niemal darmowe: to zwykła konkatenacja mniejsze + pivot + większe, bez żadnego porównywania. Mówimy więc "trudny podział, łatwe łączenie" – odwrotnie niż w sortowaniu przez scalanie, gdzie podział jest trywialny (dzielimy w połowie), a cała praca tkwi w scalaniu posortowanych połówek.
W praktyce algorytm jest szybszy od sortowania przez scalanie ze względu na lepsze wykorzystanie pamięci podręcznej procesora i mniejsze stałe czasowe.
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;
// Partycjonowanie 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 in-place 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 wersja in-place quicksortu sortuje 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 quicksortu. Sam podział (partition) 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.
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 to dlatego quicksort jest w praktyce bardzo szybki.
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 in-place partycjonuje elementy wewnątrz jednej tablicy i potrzebuje jedynie O(log n) na stos rekurencji – i to ta wartość widnieje wśród złożoności obok.
Zagadnienia z tego samego obszaru matury – warto je powtórzyć razem: