Informatyka dla klas II

Algorytm

Algorytm sortowania szybkiego opiera się na strategii "dziel i zwyciężaj" (ang. divide and conquer), którą możemy krótko scharakteryzować w trzech punktach:

1. DZIEL - problem główny zostaje podzielony na podproblemy
2. ZWYCIĘŻAJ - znajdujemy rozwiązanie podproblemów
3. POŁĄCZ - rozwiązania podproblemów zostają połączone w rozwiązanie problemu głównego

Idea sortowania szybkiego jest następująca:

prof. Tony Hoare

Sortowanie szybkie zostało wynalezione przez angielskiego informatyka, profesora Tony'ego Hoare'a w latach 60-tych ubiegłego wieku. W przypadku typowym algorytm ten jest najszybszym algorytmem sortującym z klasy złożoności obliczeniowej O(n log n) - stąd pochodzi jego popularność w zastosowaniach. Musimy jednak pamiętać, iż w pewnych sytuacjach (zależnych od sposobu wyboru piwotu oraz niekorzystnego ułożenia danych wejściowych) klasa złożoności obliczeniowej tego algorytmu może się degradować do O(n²), co więcej, poziom wywołań rekurencyjnych może spowodować przepełnienie stosu i zablokowanie komputera. Z tych powodów algorytmu sortowania szybkiego nie można stosować bezmyślnie w każdej sytuacji tylko dlatego, iż jest uważany za jeden z najszybszych algorytmów sortujących - zawsze należy przeprowadzić analizę możliwych danych wejściowych właśnie pod kątem przypadku niekorzystnego - czasem lepszym rozwiązaniem może być zastosowanie wcześniej opisanego algorytmu sortowania przez kopcowanie, który nigdy nie degraduje się do klasy O(n²).

Jako piwot można wybierać element pierwszy, środkowy, ostatni, medianę lub losowy. Dla naszych potrzeb wybierzemy element środkowy:

Dzielenie na partycje polega na umieszczeniu dwóch wskaźników na początku zbioru - i oraz j. Wskaźnik i przebiega przez zbiór poszukując wartości mniejszych od piwotu. Po znalezieniu takiej wartości jest ona wymieniana z elementem na pozycji j. Po tej operacji wskaźnik j jest przesuwany na następną pozycję. Wskaźnik j zapamiętuje pozycję, na którą trafi następny element oraz na końcu wskazuje miejsce, gdzie znajdzie się piwot. W trakcie podziału piwot jest bezpiecznie przechowywany na ostatniej pozycji w zbiorze.

Przykład:

Dla przykładu podzielimy na partycje zbiór:  { 7 2 4 7 3 1 4 6 5 8 3 9 2 6 7 6 3 }

 7 2 4 7 3 1 4 6 5 8 3 9 2 6 7 6 3 

 7 2 4 7 3 1 4 6 3 8 3 9 2 6 7 6 5 

 7 2 4 7 3 1 4 6 3 8 3 9 2 6 7 6 5 
 i 
 j 

 7 2 4 7 3 1 4 6 3 8 3 9 2 6 7 6 5 
   i 
 j 

 2 7 4 7 3 1 4 6 3 8 3 9 2 6 7 6 5 
   i 
   j 

 2 7 4 7 3 1 4 6 3 8 3 9 2 6 7 6 5 
     i 
   j 

 2 4 7 7 3 1 4 6 3 8 3 9 2 6 7 6 5 
     i 
     j 

 2 4 7 7 3 1 4 6 3 8 3 9 2 6 7 6 5 
         i 
     j 

 2 4 3 7 7 1 4 6 3 8 3 9 2 6 7 6 5 
         i 
       j 

 2 4 3 7 7 1 4 6 3 8 3 9 2 6 7 6 5 
           i 
       j 

 2 4 3 1 7 7 4 6 3 8 3 9 2 6 7 6 5 
           i 
         j 

 2 4 3 1 7 7 4 6 3 8 3 9 2 6 7 6 5 
             i 
         j 

 2 4 3 1 4 7 7 6 3 8 3 9 2 6 7 6 5 
             i 
           j 

 2 4 3 1 4 7 7 6 3 8 3 9 2 6 7 6 5 
                 i 
           j 

 2 4 3 1 4 3 7 6 7 8 3 9 2 6 7 6 5 
                 i 
             j 

 2 4 3 1 4 3 7 6 7 8 3 9 2 6 7 6 5 
                     i 
             j 

 2 4 3 1 4 3 3 6 7 8 7 9 2 6 7 6 5 
                     i 
               j 

 2 4 3 1 4 3 3 6 7 8 7 9 2 6 7 6 5 
                         i 
               j 

 2 4 3 1 4 3 3 2 7 8 7 9 6 6 7 6 5 
                         i 
                 j 

 2 4 3 1 4 3 3 2 5 8 7 9 6 6 7 6 7 
                 ^             i   
Lewa partycja    j   Prawa partycja

Po zakończeniu podziału na partycje wskaźnik j wyznacza pozycję piwotu. Lewa partycja zawiera elementy mniejsze od piwotu i rozciąga się od początku zbioru do pozycji j - 1. Prawa partycja zawiera elementy większe lub równe piwotowi i rozciąga się od pozycji j + 1 do końca zbioru. Operacja podziału na partycje ma liniową klasę złożoności obliczeniowej - O(n).

Sortuj_szybko(lewy, prawy)

Dane wejściowe

d[ ]	- Zbiór zawierający elementy do posortowania. Zakres indeksów elementów jest dowolny.
lewy	- indeks pierwszego elementu w zbiorze, lewy C
prawy	- indeks ostatniego elementu w zbiorze, prawy C

Dane wyjściowe

Zmienne pomocnicze

piwot	-	element podziałowy
i, j	-	indeksy, i, j C

Algorytm sortowania szybkiego wywołujemy podając za lewy indeks pierwszego elementu zbioru, a za prawy indeks elementu ostatniego (czyli Sortuj_szybko(0,n-1)). Zakres indeksów jest dowolny - dzięki temu ten sam algorytm może również sortować fragment zbioru, co wykorzystujemy przy sortowaniu wyliczonych partycji.

Na element podziałowy wybieramy element leżący w środku dzielonej partycji. Wyliczamy jego pozycję i zapamiętujemy ją tymczasowo w zmiennej i. Robimy to po to, aby dwukrotnie nie wykonywać tych samych rachunków.

Element d[i] zapamiętujemy w zmiennej piwot, a do d[i] zapisujemy ostatni element partycji. Dzięki tej operacji piwot został usunięty ze zbioru.

Ustawiamy zmienną j na początek partycji. Zmienna ta zapamiętuje pozycję podziału partycji.

W pętli sterowanej zmienną i przeglądamy kolejne elementy od pierwszego do przedostatniego (ostatni został umieszczony na pozycji piwotu, a piwot zapamiętany). Jeśli i-ty element jest mniejszy od piwotu, to trafia on na początek partycji - wymieniamy ze sobą elementy na pozycjach i-tej i j-tej. Po tej operacji przesuwamy punkt podziałowy partycji j.

Po zakończeniu pętli element z pozycji j-tej przenosimy na koniec partycji, aby zwolnić miejsce dla piwotu, po czym wstawiamy tam piwot. Zmienna j wskazuje zatem wynikową pozycję piwotu. Pierwotna partycja została podzielona na dwie partycje:

Sprawdzamy, czy partycje te obejmują więcej niż jeden element. Jeśli tak, to wywołujemy rekurencyjnie algorytm sortowania szybkiego przekazując mu granice wyznaczonych partycji. Po powrocie z wywołań rekurencyjnych partycja wyjściowa jest posortowana rosnąco. Kończymy algorytm.