obrazek obrazekobrazek

obrazek

Prezentowane materiały są przeznaczone dla uczniów szkół ponadgimnazjalnych.
Autor artykułu: mgr Jerzy Wałaszek,  wersja1.0

 ©2013 mgr Jerzy Wałaszek
I LO w Tarnowie

obrazek

Sortowanie szybkie

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:

 

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.

 

obrazek
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(n2), 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(n2).
 

Tworzenie partycji

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

 

Specyfikacja problemu

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 obrazek C
prawy – indeks ostatniego elementu w zbiorze, prawy obrazek C

Dane wyjściowe

T – tablica zawierający elementy posortowane rosnąco

Zmienne pomocnicze

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

 

Lista kroków

K01:
i  ← [  lewy  + prawy  ]
2
K02: piwot ← T[i];   T[i] ← T[prawy];   j ← lewy
K03: Dla i  = lewy, lewy  + 1, ..., prawy  - 1: wykonuj K04...K05
K04:     Jeśli T[i] ≥ piwot, to wykonaj kolejny obieg pętli K03
K05:     T[i] ↔ T[j];    j ← j  + 1
K06: T[prawy] ← T[j];   T[j] ← piwot
K07: Jeśli lewy  < j  - 1, to Sortuj_szybko(lewy, j  - 1)
K08: Jeśli j  + 1 < prawy, to Sortuj_szybko(j  + 1, prawy)
K09: Zakończ

 

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.

   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie
©2026 mgr Jerzy Wałaszek
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