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:

1. Dziel: tablicę wejściową podziel na dwie podtablice, od indeksu p do indeksu q, tak aby przed elementem o indeksie q 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 od pivot.

2. 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.

3. 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 miejscusortowanie w miejscu. Nie ma więc potrzeby łączenia elementów.

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.

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.

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:

funkcja sortowanieSzybkie(tablica, p, k)
	jeżeli p < k wykonaj:
    	q = podziałTablicy(tablica, p, k)
        sortowanieSzybkie(tablica, p, q)
        sortowanieSzybkie(tablica, q + 1, k)

• p to miejsce, od którego chcemy posortować tablicę; gdy chcemy wykonać sortowanie od początku tablicy, to p = 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:

funkcja podziałTablicy(tablica, p, k)
	pivot = tablica(k)
    i = p - 1
	j = k + 1
    dopóki prawda wykonuj:
    	wykonuj i = i + 1
        	dopóki i <= k oraz tablica(i) < pivot
        wykonuj j = j - 1
        	dopóki j >= p oraz tablica(j) > pivot
        jeżeli i <= j wykonaj:
        	zamień tablica(i) z tablica(j)
		w przeciwnym razie wykonaj:
            zwróć j

• 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 od pivot, 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. Zmienna pivot może być dowolnym elementem tablicy, np. pierwszym, ostatnim lub środkowym. My wybraliśmy ostatni element.

• Następnie w zmiennych i oraz j 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. Indeks j zmniejszamy, aby w końcu znaleźć element mniejszy od pivot.

• 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:

RwGFU1wdspLEn

ilustracja przedstawia złożoność O(n logarytm drugiego stopnia z n). Na schemacie po lewej stronie jest ${\text{log}}_{2 }\mathrm{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.

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 2²).

R13CeGVW0C5qo

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.

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