Quicksort - Pawel-Sk/Sortowanie GitHub Wiki

Omawiany algorytm należy do jednego z najszybszych algorytmów sortujących dane wynaleziony w 1960 roku przez Sir Charles Antony Richard Hoare. Jest on chętnie implementowany i wdrażany do systemów informatycznych ze względu na szerokie spektrum zalet:

-złożoność czasowa jest rzędu O(n log n) -algorytm nie potrzebuje dodatkowej tablicy do posortowania jak to jest w przypadku sortowania przez scalanie -jest łatwy w implementacji -dobrze współpracuje z różnymi typami danych

Algorytm posiada także wady:

-w sytuacji pesymistycznej złożoność może wynosić O(n2) -jest niestabilny -jest wrażliwy na błędy w implementacji

Działanie algorytmu

Algorytm wykorzystuje technikę "dziel i zwyciężaj". Według ustalonego schematu wybierany jest jeden element w sortowanej tablicy, który będziemy nazywać pivot. Pivot może być elementem środkowym, pierwszym, ostatnim, losowym lub wybranym według jakiegoś innego schematu dostosowanego do zbioru danych. Następnie ustawiamy elementy nie większe na lewo tej wartości, natomiast nie mniejsze na prawo. W ten sposób powstaną nam dwie części tablicy (niekoniecznie równe), gdzie w pierwszej części znajdują się elementy nie większe od drugiej. Następnie każdą z tych podtablic sortujemy osobno według tego samego schematu.