Quicksort czyli sortowanie szybkie to algorytm działający na zasadzie "dziel i zwyciężaj".

Opis działania algorytmu

Z tablicy wybieramy element rozdzielający (tzw pivot), za pomocą tego elementu tablica zostaje dzielona na dwa fragmenty: do lewej przenoszone są wszystkie wartości nie większe od pivota, do prawego wszystkie większe. Następnie sortujemy osobno obie części (prawą i lewą) tą samą metodą. Rekurencja kończy się, gdy kolejny fragment uzyskany z podziału zawiera pojedynczy element, jako że jednoelementowa tablica nie wymaga sortowania.

Złożoność algorytmu zależy od sposobu wyboru pivota. Jeśli uda się tak wybrać pivota, że podziały są zrównoważone, algorytm jest tak szybki jak sortowanie przez scalanie czyli O(n·logn); w przeciwnym przypadku może działać tak wolno jak sortowanie przez wstawianie (O(n²)). Średni czas działania przy losowym wyborze elementu rozdzielającego, dorównuje przypadkowi optymistycznemu.

Poniżej pseudokod algorytmu:

Kliknij by zobaczyć interpretację taneczną algorytmu ;)