Klasa II - sortowanie danych

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:

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

Idea sortowania szybkiego jest następująca:

DZIEL :	najpierw sortowany zbiór dzielimy na dwie części w taki sposób, aby wszystkie elementy leżące w pierwszej części (zwanej lewą partycją) były mniejsze lub równe od wszystkich elementów drugiej części zbioru (zwanej prawą partycją).
ZWYCIĘŻAJ :	każdą z partycji sortujemy rekurencyjnie tym samym algorytmem.
POŁĄCZ :	połączenie tych dwóch partycji w jeden zbiór daje w wyniku zbiór posortowany.

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

Do utworzenia partycji musimy ze zbioru wybrać jeden z elementów, który nazwiemy piwotem. W lewej partycji znajdą się wszystkie elementy niewiększe od piwotu, a w prawej partycji umieścimy wszystkie elementy niemniejsze od piwotu. Położenie elementów równych nie wpływa na proces sortowania, zatem mogą one występować w obu partycjach. Również porządek elementów w każdej z partycji nie jest ustalony.

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

piwot ← T[(lewy + prawy) div 2]

piwot	- element podziałowy
T	- dzielona tablica
lewy	- indeks pierwszego elementu
prawy	- indeks ostatniego elementu

Dzielenie na partycje polega na umieszczeniu dwóch wskaźników na początku tablicy - 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 tablicy.

Przykład:

Dla przykładu podzielimy na partycje tablicę:

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

Lp.	Operacja	Opis
1.	7 2 4 7 3 1 4 6 5 8 3 9 2 6 7 6 3	Wyznaczamy na piwot element środkowy.
2.	7 2 4 7 3 1 4 6 3 8 3 9 2 6 7 6 5	Piwot wymieniamy z ostatnim elementem tablicy
3.	7 2 4 7 3 1 4 6 3 8 3 9 2 6 7 6 5 i j	Na początku tablicy ustawiamy dwa wskaźniki. Wskaźnik i będzie przeglądał tablicę do przedostatniej pozycji. Wskaźnik j zapamiętuje miejsce wstawiania elementów mniejszych od piwotu
4.	7 2 4 7 3 1 4 6 3 8 3 9 2 6 7 6 5 i j	Wskaźnikiem i szukamy elementu mniejszego od piwotu
5.	2 7 4 7 3 1 4 6 3 8 3 9 2 6 7 6 5 i j	Znaleziony element wymieniamy z elementem na pozycji j-tej. Po wymianie wskaźnik j przesuwamy o 1 pozycję.
6.	2 7 4 7 3 1 4 6 3 8 3 9 2 6 7 6 5 i j	Szukamy
7.	2 4 7 7 3 1 4 6 3 8 3 9 2 6 7 6 5 i j	Wymieniamy i przesuwamy j.
8.	2 4 7 7 3 1 4 6 3 8 3 9 2 6 7 6 5 i j	Szukamy
9.	2 4 3 7 7 1 4 6 3 8 3 9 2 6 7 6 5 i j	Wymieniamy i przesuwamy j.
10.	2 4 3 7 7 1 4 6 3 8 3 9 2 6 7 6 5 i j	Szukamy
11.	2 4 3 1 7 7 4 6 3 8 3 9 2 6 7 6 5 i j	Wymieniamy i przesuwamy j.
12.	2 4 3 1 7 7 4 6 3 8 3 9 2 6 7 6 5 i j	Szukamy
13.	2 4 3 1 4 7 7 6 3 8 3 9 2 6 7 6 5 i j	Wymieniamy i przesuwamy j.
14.	2 4 3 1 4 7 7 6 3 8 3 9 2 6 7 6 5 i j	Szukamy
15.	2 4 3 1 4 3 7 6 7 8 3 9 2 6 7 6 5 i j	Wymieniamy i przesuwamy j.
16.	2 4 3 1 4 3 7 6 7 8 3 9 2 6 7 6 5 i j	Szukamy
17.	2 4 3 1 4 3 3 6 7 8 7 9 2 6 7 6 5 i j	Wymieniamy i przesuwamy j.
18.	2 4 3 1 4 3 3 6 7 8 7 9 2 6 7 6 5 i j	Szukamy
19.	2 4 3 1 4 3 3 2 7 8 7 9 6 6 7 6 5 i j	Wymieniamy i przesuwamy j.
20.	2 4 3 1 4 3 3 2 5 8 7 9 6 6 7 6 7 ^ i Lewa partycja j Prawa partycja	Brak dalszych elementów do wymiany. Piwot wymieniamy z elementem na pozycji j-tej. Podział na partycje zakończony.

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 tablicy. Operacja podziału na partycje ma liniową klasę złożoności obliczeniowej - O(n).

Sortuj_szybko(lewy, prawy)

Dane wejściowe

T	– tablica 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

T	– tablica zawierający elementy posortowane rosnąco

Zmienne pomocnicze

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

Algorytm sortowania szybkiego wywołujemy podając za lewy indeks pierwszego elementu tablicy, 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 tablicy, co wykorzystujemy przy sortowaniu wyznaczonych partycji.

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.

Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl

W artykułach serwisu są używane cookies. Jeśli nie chcesz ich otrzymywać,
zablokuj je w swojej przeglądarce.
Informacje dodatkowe

Sortowanie szybkie

Tworzenie partycji

Specyfikacja problemu

Sortuj_szybko(lewy, prawy)

Dane wejściowe

Dane wyjściowe

Zmienne pomocnicze

Lista kroków