Przeczytaj
Działanie algorytmu quick sort
Zasada działania algorytmu quick sort jest oparta na metodzie „dziel i zwyciężaj”.
W odniesieniu do sortowania szybkiego możemy ją przedstawić w trzech krokach:
Dziel: tablicę wejściową podziel na dwie podtablice, od indeksu
p
do indeksuq
, tak aby przed elementem o indeksieq
znalazły się elementy mniejsze lub równe elementowi osiowemu (ang. pivot), natomiast za tym elementem – większe lub równe. W ten sposób otrzymamy jedną tablicę o wartościach nie większych oraz drugą o wartościach nie mniejszych odpivot
.Zwyciężaj: dla powstałych w ten sposób dwóch podtablic wywołujemy rekurencyjnie funkcję sortowania szybkiego, która ponownie dzieli je na dwie podtablice i tak do momentu, aż uzyskamy tablice jednoelementowe.
Połącz: powstałe podtablice są zazwyczaj łączone w jedną, posortowaną całość. Jednak w przypadku sortowania szybkiego, będziemy wykonywać sortowanie w miejscusortowanie w miejscu. Nie ma więc potrzeby łączenia elementów.
![](https://static.zpe.gov.pl/portal/f/res-minimized/Rbb9mVRZrQpqS/1690813914/XodgjMGChWo3m94WgMCbgsBL3Ez4Dx6T.png)
Film dostępny pod adresem /preview/resource/Rbb9mVRZrQpqS
Animacja przedstawia sortowanie wąskich kolumn od najniższej do najwyższej. Sortowanie przebiega bardzo szybko. Początkowo kolumny podlegające sortowaniu są różnej wielkości, są wymieszane. Następnie za pomocą przemieszczającej się strzałki w postaci łuku kolumny są porównywane i przestawiane od najniższej do najwyższej.
Pseudokod sortowania quick sort
Przeanalizujmy pseudokod sortowania quick sort:
p
to miejsce, od którego chcemy posortować tablicę; gdy chcemy wykonać sortowanie od początku tablicy, top = 1
,k
to miejsce zakończenia sortowania,q
to punkt podziału tablicy.
Rozpoczynamy funkcję sortowanieSzybkie
dla całej tablicy, którą chcemy posortować. Jeżeli p
jest mniejsze od k
, czyli tablica składa się z więcej niż jednego elementu, to wykonujemy następujące czynności. Wywołujemy funkcję podziałTablicy
, która dzieli tablicę na dwie podtablice, a punkt podziału zapisuje w zmiennej q
. Teraz rekurencyjnie wywołujemy funkcję sortowanieSzybkie
dla podtablic. Algorytm kończy działanie, gdy w wyniku podziału pozostaną tablice jednoelementowe.
Pseudokod funkcji podziałTablicy
wygląda następująco:
Za pomocą zmiennej
pivot
zapisujemy liczbę, która odpowiada za to, w której podtablicy umieścimy każdy z elementów. Jeżeli rozpatrywana liczba będzie mniejsza odpivot
, umieścimy ją w tablicy pierwszej, jeżeli większa, to w drugiej, a jeżeli równa, to może pojawić się zarówno w pierwszej, jak i drugiej. Zmiennapivot
może być dowolnym elementem tablicy, np. pierwszym, ostatnim lub środkowym. My wybraliśmy ostatni element.
Następnie w zmiennych
i
orazj
zapisujemy miejsca przed pierwszym oraz za ostatnim elementem tablicy, którą chcemy posortować.
Zwiększamy wówczas indeks
i
, do momentu znalezienia elementu tablicy większego niżpivot
. Indeksj
zmniejszamy, aby w końcu znaleźć element mniejszy odpivot
.
Po znalezieniu mniejszego elementu zmieniamy te elementów, aby uzyskać w podtablicach odpowiednie wartości.
Wymienione dwa punkty, opisujące czynności zamiany, wykonujemy do momentu, gdy
i
osiągnie wartość większą niżj
.
W tym momencie funkcja zwraca indeks
j
, czyli punkt podziału tablicy.
Czas działania algorytmu
Złożoność obliczeniowa algorytmu sortowania szybkiego jest zależna od rozmiarów części, na jakie jest dzielona tablica. Jeżeli za każdym razem będzie wybierany pivot
o wartości najmniejszej lub największej w tablicy, podział tablicy będzie nierównomierny. Tym samym poważnie wzrośnie czas działania algorytmu. W takim ujęciu przypadek optymistyczny i pesymistyczny nie są związane ze sposobem uporządkowania elementów w tablicy, ale z wyborem elementu osiowego, czyli ze sposobem dzielenia tablicy.
Rozważmy najpierw przypadek optymistyczny, którego złożoność obliczeniowa algorytmu wynosi O(n log n). Jeżeli tablica za każdym razem jest dzielona na dwie równe części, otrzymamy właśnie taki czas działania. Przedstawia to poniższy schemat:
![ilustracja przedstawia złożoność O(n logarytm drugiego stopnia z n). Na schemacie po lewej stronie jest log2 n. Następnie jest duża, pionowa klamra. Po prawej stronie klamry jest schemat. Na górze schematu litera n. Od litery n kreski w dół na lewo i prawo. Tam zapis n/2. Od każdego n/2 kreski do n/4 - dwa razy do każdego n/2. Od każdego n/2 po dwie kreski w dół do zapisu n/8. Na samym dole schematu czterokrotnie są trzy czerwone kropki. Po prawej stronie od n, n/2, n/4 oraz n/8 jest pozioma strzałka skierowana w stronę zapisu. Na początku każdej strzałki jest litera n.](https://static.zpe.gov.pl/portal/f/res-minimized/RwGFU1wdspLEn/1690813915/1DEDiiRZBEg0afr3zxdcXgJtNgCuH1UK.png)
W przypadku pesymistycznym tablica jest dzielona na dwie części, z których jedna zawiera jeden element, a druga resztę elementów. Złożoność obliczeniowa wynosi wtedy O(nIndeks górny 22).
![Ilustracja przedstawia złożoność O(n kwadrat). Po lewej stronie ilustracji jest litera n, a obok niej pionowa otwarta klamra. Po prawej stronie klamry jest następujący schemat: z litery n wychodzą dwie linie - do 1 oraz n‑1, z n‑1 linia do 1 oraz n‑2, z n‑2 do 1 i n‑3. Z n‑3 trzy czerwone kropki biegną do cyfry 2. Od cyfry 2 linie do 1 oraz 1. Następnie do liczby dwa, z których linie idą do 1 i 1. Od góry schematu po prawej stronie od n jest pozioma strzałka w jego kierunku na początku strzałki jest litera n. Przy n‑1 po prawej stronie jest pozioma strzałka w kierunku zapisu, na początku strzałki jest litera n. Po prawej stronie od n‑2 jest pozioma strzałka w kierunku zapisu, na początku strzałki jest zapis n‑1. Po prawej stronie n‑3 jest pozioma strzałka w kierunku zapisu, na początku strzałki jest zapis n‑2. Od n‑2 trzy czerwone kropki w dół do liczby 2. Od liczby 2 strzałka w kierunku 1, które jest na samym dole po prawej stronie schematu.](https://static.zpe.gov.pl/portal/f/res-minimized/R13CeGVW0C5qo/1690813916/1cpd1qM17NLWMYBE8fDdRRS9hNVh0lG6.png)
Algorytm sortowania szybkiego – złożoność obliczeniowa
Założeniem algorytmu sortowania szybkiego jest – jak sama nazwa wskazuje – możliwie najkrótszy czas sortowania kosztem większego wykorzystania pamięci (wywołania rekurencyjne).
Średnia złożoność obliczeniowa algorytmu szybkiego sortowania wynosi:
Złożoność obliczeniowa takiego algorytmu w przypadku pesymistycznym to:
Natomiast jego złożoność obliczeniowa w przypadku optymistycznym to:
Słownik
algorytmy sortowania, w których elementy znajdują się cały czas w początkowej tablicy i nie jest potrzebna dodatkowa pamięć
element osiowy – element tablicy wybrany wedle ustalonego schematu; jest to element dzielący tablicę