Sortowanie szybkie: Różnice pomiędzy wersjami
[wersja przejrzana] | [wersja przejrzana] |
m →Ograniczenie rekursji: drobne merytoryczne, drobne techniczne |
m MalarzBOT: likwiduję Błędy składniowe: Przestarzałe znaczniki HTML |
||
(Nie pokazano 40 wersji utworzonych przez 30 użytkowników) | |||
Linia 1: | Linia 1: | ||
{{Algorytm infobox |
{{Algorytm infobox |
||
|nazwa = Sortowanie szybkie |
|||
|grafika=Sorting_quicksort_anim.gif |
|grafika = Sorting_quicksort_anim.gif |
||
⚫ | |||
|wielkość grafiki = |
|||
⚫ | |||
|opis grafiki = |
|||
|czas=średnio: О(''n''·log''n'')<br/>pesymistycznie: O(''n''<sup>2</sup>) |
|||
⚫ | |||
⚫ | |||
⚫ | |||
|czas = <math>O(n \log n)</math><br />pesymistycznie: <math>O(n^2)</math> |
|||
⚫ | |||
}} |
}} |
||
'''Sortowanie szybkie''' ([[Język angielski|ang.]] |
'''Sortowanie szybkie''' ([[Język angielski|ang.]] ''quicksort'') – jeden z popularnych [[algorytm]]ów [[sortowanie|sortowania]] działających na zasadzie „[[dziel i zwyciężaj]]”<ref name="CLR">{{Cytuj książkę |nazwisko = Thomas H. Cormen, Charles E. Leiserson, Ronald. R. Rivest |tytuł = Wprowadzenie do algorytmów |data = 1997, 1998 |wydawca = Wydawnictwa Naukowo-Techniczne |miejsce = Warszawa |isbn = 83-204-2317-1 |strony = 186–205}}</ref>. |
||
Sortowanie QuickSort zostało wynalezione w [[1962 w informatyce|1962]] przez [[ |
Sortowanie szybkie (ang. QuickSort) zostało wynalezione w [[1962 w informatyce|1962]] przez [[Charles Antony Richard Hoare|C.A.R. Hoare’a]]<ref name="Hoare">C.A.R. Hoare: ''Quicksort.'' Computer Journal, Vol. 5, 1, 10–15 (1962).</ref>. |
||
Algorytm sortowania szybkiego jest wydajny: jego średnia [[złożoność obliczeniowa]] jest [[ |
Algorytm sortowania szybkiego jest wydajny: jego średnia [[złożoność obliczeniowa]] jest [[Asymptotyczne tempo wzrostu|rzędu]] <math>O(n \log n)</math><ref name="CLR" />. Ze względu na szybkość i prostotę [[Implementacja (informatyka)|implementacji]] jest powszechnie używany. Jego implementacje znajdują się w bibliotekach standardowych wielu środowisk programowania<ref>Uwaga dot. implementacji algorytmu Quicksort w funkcji <code>sort()</code> języka [[PHP]]: {{cytuj stronę |url=http://php.net/manual/en/function.sort.php#refsect1-function.sort-notes |tytuł=PHP: sort - Manual |język=en |data dostępu=2014-03-28}}</ref><ref>Opis funkcji <code>qsort</code> z [[Biblioteka standardowa|biblioteki standardowej]] języka [[C++]]: {{cytuj stronę |url=http://www.cplusplus.com/reference/cstdlib/qsort/ |tytuł=qsort - C++ Reference |język=en |data dostępu=2014-03-28}}</ref>. |
||
== Algorytm == |
== Algorytm == |
||
Z tablicy wybiera się element rozdzielający, po czym tablica jest dzielona na dwa fragmenty: do początkowego przenoszone są wszystkie elementy nie większe od rozdzielającego, do końcowego wszystkie większe. Potem sortuje się osobno początkową i końcową część tablicy<ref name="CLR"/>. Rekursja kończy się, gdy kolejny fragment uzyskany z podziału zawiera pojedynczy element, jako że jednoelementowa tablica nie wymaga sortowania. |
Z tablicy wybiera się element rozdzielający, po czym tablica jest dzielona na dwa fragmenty: do początkowego przenoszone są wszystkie elementy nie większe od rozdzielającego, do końcowego wszystkie większe. Potem sortuje się osobno początkową i końcową część tablicy<ref name="CLR" />. Rekursja kończy się, gdy kolejny fragment uzyskany z podziału zawiera pojedynczy element, jako że jednoelementowa tablica nie wymaga sortowania. |
||
Jeśli przez '''l''' oznacza się indeks pierwszego, a przez '''r''' – ostatniego elementu sortowanego fragmentu tablicy, zaś przez '''i''' – indeks elementu, na którym tablica została podzielona, to procedurę sortowania można (w dużym uproszczeniu) przedstawić następującym pseudokodem: |
Jeśli przez '''l''' oznacza się indeks pierwszego, a przez '''r''' – ostatniego elementu sortowanego fragmentu tablicy, zaś przez '''i''' – indeks elementu, na którym tablica została podzielona, to procedurę sortowania można (w dużym uproszczeniu) przedstawić następującym pseudokodem{{fakt|data=2015-01}}: |
||
< |
<syntaxhighlight lang="pascal"> |
||
PROCEDURE Quicksort(l, r) |
PROCEDURE Quicksort(tablica, l, r) |
||
BEGIN |
BEGIN |
||
IF l < r THEN |
IF l < r THEN { jeśli fragment dłuższy niż 1 element } |
||
BEGIN |
BEGIN |
||
i = PodzielTablice(l, r); |
i := PodzielTablice(tablica, l, r); { podziel i zapamiętaj punkt podziału } |
||
Quicksort(l, i-1); { posortuj lewą część } |
Quicksort(tablica, l, i-1); { posortuj lewą część } |
||
Quicksort(i+1, r); { posortuj prawą część } |
Quicksort(tablica, i+1, r); { posortuj prawą część } |
||
END |
END |
||
END |
END |
||
</source> |
|||
{wybiera element, który ma być użyty do podziału |
|||
⚫ | Właściwe działanie algorytmu wymaga, aby procedura <code>PodzielTablice</code> pozostawiała element rozdzielający na końcu lewej części uzyskanej z podziału. Wówczas element ten znajduje się na swojej ostatecznej pozycji i nie podlega dalszemu przetwarzaniu – rekurencyjne wywołania <code>Quicksort</code> nie obejmują indeksu '''i'''. Tym samym do dalszego przetwarzania przekazuje się o jeden element mniej, co gwarantuje zakończenie rekurencji. |
||
i przenosi wszystkie elementy mniejsze na lewo od |
|||
tego elementu, a elementy większe lub równe, na prawo |
|||
od wybranego elementu } |
|||
PROCEDURE PodzielTablice(tablica, l, r) |
|||
BEGIN |
|||
indeksPodzialu := WybierzPunktPodzialu(l, r); {wybierz element, który posłuży do podziału tablicy} |
|||
wartoscPodzialu := tablica[indeksPodzialu]; {zapamiętaj wartość elementu} |
|||
Zamien(tablica, indeksPodzialu, r); {przenieś element podziału na koniec tablicy, aby sam nie brał udziału w podziale} |
|||
aktualnaPozycja := l; |
|||
FOR i:=l TO r-1 DO {iteruj przez wszystkie elementy, jeśli element jest mniejszy niż wartość elementu podziału dodaj go do "lewej" strony} |
|||
BEGIN |
|||
IF tablica[i] < wartoscPodzialu THEN |
|||
BEGIN |
|||
Zamien(tablica, i, aktualnaPozycja); |
|||
aktualnaPozycja := aktualnaPozycja + 1; |
|||
END |
|||
END |
|||
Zamien(tablica, aktualnaPozycja, r); {wstaw element podziału we właściwe miejsce} |
|||
return aktualnaPozycja; |
|||
END |
|||
{ podstawowa implementacja wyboru punktu podziału - wybiera element "środkowy" w tablicy } |
|||
PROCEDURE WybierzPunktPodzialu(l, r) |
|||
BEGIN |
|||
return l + (r-l) div 2; |
|||
END |
|||
{ zamienia miejscami elementy w komórkach i1, i2 } |
|||
PROCEDURE Zamien(tablica, i1, i2) |
|||
BEGIN |
|||
IF i1<>i2 THEN |
|||
BEGIN |
|||
aux := tablica[i1]; |
|||
tablica[i1] := tablica[i2]; |
|||
tablica[i2] := aux; |
|||
END |
|||
END |
|||
</syntaxhighlight> |
|||
⚫ | Właściwe działanie algorytmu wymaga, aby procedura <code>PodzielTablice</code> pozostawiała element rozdzielający na końcu lewej części uzyskanej z podziału. Wówczas element ten znajduje się na swojej ostatecznej pozycji i nie podlega dalszemu przetwarzaniu – rekurencyjne wywołania <code>Quicksort</code> nie obejmują indeksu '''i'''. Tym samym do dalszego przetwarzania przekazuje się o jeden element mniej, co gwarantuje zakończenie [[Rekurencja|rekurencji]]. |
||
== Złożoność == |
== Złożoność == |
||
Złożoność algorytmu zależy od wyboru elementu rozdzielającego; jeśli podziały są zrównoważone algorytm jest tak szybki jak [[sortowanie przez scalanie]] czyli O( |
Złożoność algorytmu zależy od wyboru elementu rozdzielającego; jeśli podziały są zrównoważone algorytm jest tak szybki jak [[sortowanie przez scalanie]], czyli <math>O(n \cdot \log n);</math> w przeciwnym przypadku może działać tak wolno jak [[sortowanie przez wstawianie]] <math>(O(n^2)).</math> Średni czas działania przy losowym wyborze elementu rozdzielającego, dorównuje przypadkowi optymistycznemu<ref name="CLR" />. |
||
=== Przypadek optymistyczny === |
=== Przypadek optymistyczny === |
||
Linia 44: | Linia 87: | ||
=== Przypadek przeciętny === |
=== Przypadek przeciętny === |
||
W przypadku przeciętnym, to jest dla równomiernego rozkładu prawdopodobieństwa wyboru elementu z tablicy: |
W przypadku przeciętnym, to jest dla równomiernego [[Rozkład prawdopodobieństwa|rozkładu prawdopodobieństwa]] wyboru elementu z tablicy: |
||
: <math>T(n) \approx 2 n \ln n \approx 1 |
: <math>T(n) \approx 2 n \ln n \approx 1{,}39 n\log_2 n</math> |
||
złożoność jest |
złożoność jest o 39% wyższa niż w przypadku optymistycznym. |
||
=== Przypadek pesymistyczny === |
=== Przypadek pesymistyczny === |
||
W przypadku pesymistycznym, jeśli zawsze wybierzemy element najmniejszy (albo największy) w sortowanym fragmencie tablicy, to: |
W przypadku pesymistycznym, jeśli zawsze wybierzemy [[Elementy najmniejszy i największy|element najmniejszy]] (albo największy) w sortowanym fragmencie tablicy, to: |
||
: <math>T(n) = n-1 + T(n-1) |
: <math>T(n) = n-1 + T(n-1)</math> |
||
skąd wynika kwadratowa złożoność czasowa: |
skąd wynika kwadratowa złożoność czasowa: |
||
: <math>T(n) = \frac{n^2-n}2 \approx \frac {n^2} 2</math> |
: <math>T(n) = \frac{n^2-n}2 \approx \frac {n^2} 2</math> |
||
W tym przypadku otrzymuje się też olbrzymią, liniową złożoność pamięciową: |
W tym przypadku otrzymuje się też olbrzymią, liniową złożoność pamięciową: |
||
: <math>M(n) = n-1 |
: <math>M(n) = n-1</math> |
||
== Usprawnienia algorytmu == |
== Usprawnienia algorytmu == |
||
=== Wybór elementu === |
=== Wybór elementu === |
||
Najprostsza, |
Najprostsza, „naiwna” metoda podziału – wybieranie zawsze skrajnego elementu tablicy – dla danych już uporządkowanych daje katastrofalną złożoność <math>O(n^2).</math> Trywialne na pozór zadanie posortowania posortowanej tablicy okazuje się dla tak zapisanego algorytmu zadaniem skrajnie trudnym. Aby uchronić się przed takim przypadkiem stosuje się najczęściej randomizację wyboru albo wybór „środkowy z trzech”. Pierwszy sposób opiera się na losowaniu elementu rozdzielającego, co sprowadza prawdopodobieństwo zajścia najgorszego przypadku do wartości zaniedbywalnie małych. Drugi sposób polega na wstępnym wyborze trzech elementów z rozpatrywanego fragmentu tablicy, i użyciu jako elementu osiowego tego z trzech, którego wartość leży pomiędzy wartościami pozostałych dwu. Można również uzupełnić algorytm o poszukiwanie przybliżonej [[mediana|mediany]] (patrz poniżej: [[#Gwarancja złożoności|Gwarancja złożoności]]). |
||
=== Ograniczenie rekursji === |
=== Ograniczenie rekursji === |
||
Wysoka wydajność algorytmu sortowania szybkiego predestynuje go do przetwarzania dużych tablic. Takie zastosowanie wymaga jednak zwrócenia szczególnej uwagi na głębokość rekursji. Głębokość rekursji wiąże się bowiem z wykorzystaniem stosu maszynowego. |
Wysoka wydajność algorytmu sortowania szybkiego predestynuje go do przetwarzania dużych tablic. Takie zastosowanie wymaga jednak zwrócenia szczególnej uwagi na głębokość rekursji. Głębokość rekursji wiąże się bowiem z wykorzystaniem stosu maszynowego. |
||
W najgorszym przypadku, jeśli algorytm będzie dzielił tablicę zawsze na część jednoelementową i resztę, to rekursja osiągnie głębokość |
W najgorszym przypadku, jeśli algorytm będzie dzielił tablicę zawsze na część jednoelementową i resztę, to rekursja osiągnie głębokość <math>n-1.</math> Aby temu zapobiec, należy sprawdzać, która część jest krótsza – i tę porządkować najpierw. Z dłuższą zaś nie wchodzić w rekursję, lecz ponownie dzielić na tym samym poziomie wywołania: |
||
< |
<syntaxhighlight lang="pascal"> |
||
PROCEDURE Quicksort( l, r ) |
PROCEDURE Quicksort( l, r ) |
||
BEGIN |
BEGIN |
||
Linia 82: | Linia 125: | ||
END |
END |
||
END |
END |
||
</syntaxhighlight> |
|||
</source> |
|||
Przy takiej organizacji pracy na stosie zawsze pozostają zapamiętane (w zmiennych {{nowrap|'''i''', '''r'''}} albo {{nowrap|'''l''', '''i'''}}) indeksy ograniczające dłuższą, jeszcze nie posortowaną część tablicy, a wywołanie rekurencyjne zajmuje się częścią krótszą. To znaczy, że na każdym poziomie wywołań algorytm obsługuje fragment będący co najwyżej połową fragmentu z poprzedniego poziomu. Stąd wynika, że poziomów wywołań w najgorszym przypadku nie będzie więcej |
Przy takiej organizacji pracy na stosie zawsze pozostają zapamiętane (w zmiennych {{nowrap|'''i''', '''r'''}} albo {{nowrap|'''l''', '''i'''}}) indeksy ograniczające dłuższą, jeszcze nie posortowaną część tablicy, a wywołanie rekurencyjne zajmuje się częścią krótszą. To znaczy, że na każdym poziomie wywołań algorytm obsługuje fragment będący co najwyżej połową fragmentu z poprzedniego poziomu. Stąd wynika, że poziomów wywołań w najgorszym przypadku nie będzie więcej niż '''log<sub>2</sub>''n''''', gdzie ''n'' oznacza długość całej tablicy. Zatem usprawnienie to zmienia asymptotyczne wykorzystanie pamięci przez algorytm w pesymistycznym przypadku z <math>O(n)</math> do <math>O(\log n).</math> |
||
=== Quicksort w miejscu === |
=== Quicksort w miejscu === |
||
Istnieje modyfikacja czyniąca algorytm quicksort [[algorytm in situ|działającym w miejscu]]. W oryginalnym sortowaniu szybkim używa się rekursji lub [[stos (informatyka)|stosu]] (''de facto'' oba sposoby niewiele się różnią – rekursja w uproszczeniu jest niejawnym stosem) do zapamiętywania miejsc podziału. Więc chociaż algorytm w obu wersjach nie korzysta z dodatkowych tablic o rozmiarze zależnym od rozmiaru danych wejściowych, to nie można nazywać go działającym w miejscu, gdyż wysokość, a więc i wymagania pamięciowe wywołań rekursji/stosu są ściśle zależne od rozmiaru danych początkowych. |
Istnieje modyfikacja czyniąca algorytm quicksort [[algorytm in situ|działającym w miejscu]]. W oryginalnym sortowaniu szybkim używa się rekursji lub [[stos (informatyka)|stosu]] (''de facto'' oba sposoby niewiele się różnią – rekursja w uproszczeniu jest niejawnym stosem) do zapamiętywania miejsc podziału. Więc chociaż algorytm w obu wersjach nie korzysta z dodatkowych tablic o rozmiarze zależnym od rozmiaru danych wejściowych, to nie można nazywać go działającym w miejscu, gdyż wysokość, a więc i wymagania pamięciowe wywołań rekursji/stosu są ściśle zależne od rozmiaru danych początkowych. |
||
Załóżmy, że dla sortowanej tablicy ''A'' funkcja ''PodzielTablice(l,p)'' zwróciła wartość ''s''. W oryginalnym algorytmie quicksort powinno zostać wykonane wywołania ''Quicksort(l,s-1)'' i ''Quicksort(s+1,p)''. Zamiast tego |
Załóżmy, że dla sortowanej tablicy ''A'' funkcja ''PodzielTablice(l,p)'' zwróciła wartość ''s''. W oryginalnym algorytmie quicksort powinno zostać wykonane wywołania ''Quicksort(l,s-1)'' i ''Quicksort(s+1,p)''. Zamiast tego „zajmujemy się” tylko ''Quicksort(l,s-1)'', a pozycje ''s+1'' i ''p'' zapamiętujemy w następujący sposób: |
||
* s+1: jest jednoznacznie wyznaczona przez koniec ciągu '' |
* s+1: jest jednoznacznie wyznaczona przez koniec ciągu (''l,s-1'') → ''(s+1) = (s-1) + 2'' |
||
* p: znajdujemy maksimum ciągu '' |
* p: znajdujemy maksimum ciągu (''s+1,p'') i zamieniamy tę pozycję z pozycją ''s''. Aby odtworzyć pozycję ''p'', wystarczy przeszukiwać ciąg w prawo do znalezienia elementu większego od wartości stojącej na pozycji ''s''. Wtedy indeks elementu o najmniejszej wartości większej od ''A[s]'' to ''p+1''. |
||
Metoda ta sprowadza koszt pamięciowy algorytmu do wartości stałej, ''O''(1), wymaga jednak dodatkowego nakładu czasu na wyszukiwanie maksymalnych elementów kolejno sortowanych fragmentów tablicy. Ujmuje więc algorytmowi jego główną zaletę, wpisaną nawet w jego nazwę – szybkość działania. |
Metoda ta sprowadza koszt pamięciowy algorytmu do wartości stałej, ''O''(1), wymaga jednak dodatkowego nakładu czasu na wyszukiwanie maksymalnych elementów kolejno sortowanych fragmentów tablicy. Ujmuje więc algorytmowi jego główną zaletę, wpisaną nawet w jego nazwę – szybkość działania. |
||
=== Drobne fragmenty === |
=== Drobne fragmenty === |
||
U podstaw kolejnego usprawnienia leży spostrzeżenie, że około połowa wszystkich rekurencyjnych wywołań procedury dotyczy jednoelementowych fragmentów tablicy – a więc fragmentów z definicji posortowanych. Co więcej, po wliczeniu dodatkowej pracy potrzebnej na wybór elementu dzielącego i zorganizowanie pętli dzielącej tablicę okazuje się, że sortowanie tablic nawet kilkuelementowych algorytmem '''quicksort''' jest bardziej pracochłonne |
U podstaw kolejnego usprawnienia leży spostrzeżenie, że około połowa wszystkich rekurencyjnych wywołań procedury dotyczy jednoelementowych fragmentów tablicy – a więc fragmentów z definicji posortowanych. Co więcej, po wliczeniu dodatkowej pracy potrzebnej na wybór elementu dzielącego i zorganizowanie pętli dzielącej tablicę okazuje się, że sortowanie tablic nawet kilkuelementowych algorytmem '''quicksort''' jest bardziej pracochłonne niż jakimś algorytmem prostym, na przykład [[Sortowanie przez wstawianie|przez wstawianie]]. |
||
Warto więc zaniechać dalszych podziałów, gdy uzyskane fragmenty staną się dostatecznie krótkie – rzędu kilku lub kilkunastu elementów. Otrzymuje się w wyniku tablicę |
Warto więc zaniechać dalszych podziałów, gdy uzyskane fragmenty staną się dostatecznie krótkie – rzędu kilku lub kilkunastu elementów. Otrzymuje się w wyniku tablicę „prawie posortowaną”, w której większość elementów może nie znajduje się na właściwych miejscach, ale są ''blisko'' właściwych miejsc. Taką tablicę ostatecznie sortuje się algorytmem [[Sortowanie przez wstawianie|wstawiania]], który bardzo efektywnie radzi sobie z tego rodzaju danymi. Jak pokazuje praktyka, wybór granicznej długości fragmentu (progu „odcięcia” rekursji, ang. ''cutoff'') nie wymaga szczególnych rygorów – algorytm działa niemal równie dobrze dla wartości od 5 do 25. W większości zastosowań pozwala to osiągnąć oszczędność łącznego czasu wykonania rzędu 20%<ref>{{cytuj książkę |nazwisko=Bentley |imię=Jon |autor link=Jon Bentley |tytuł=Perełki oprogramowania |url= |inni=tłum. Agata Tomaszewska |wydanie=2 |wydawca=[[Wydawnictwa Naukowo-Techniczne|WNT]] |miejsce=Warszawa |rok=2001 |strony=151, 277 |seria=Klasyka Informatyki |isbn=83-204-2627-8}}</ref>. |
||
{{cytuj książkę |nazwisko=Bentley |imię=Jon |autor link=Jon Bentley |inni=tłum. Agata Tomaszewska |tytuł=Perełki oprogramowania |url= |wydanie=2 |wydawca=[[Wydawnictwa Naukowo-Techniczne|WNT]] |miejsce=Warszawa |rok=2001 |strony=151,277 |seria=Klasyka Informatyki |isbn=83-204-2627-8}} |
|||
</ref>. |
|||
=== Gwarancja złożoności === |
=== Gwarancja złożoności === |
||
Pomimo wszelkich usprawnień, pozostaje jednak, zazwyczaj znikome, prawdopodobieństwo zajścia przypadku pesymistycznego, w którym złożoność czasowa wynosi <math>O(n^2)</math> |
Pomimo wszelkich usprawnień, pozostaje jednak, zazwyczaj znikome, prawdopodobieństwo zajścia przypadku pesymistycznego, w którym złożoność czasowa wynosi <math>O(n^2).</math> Jeśli chcemy mieć pewność wykonania sortowania w czasie nie dłuższym niż <math>O(n \log_2 n),</math> należy uzupełnić algorytm o poszukiwanie przybliżonej [[mediana|mediany]], czyli elementu dzielącego posortowaną tablicę na tyle dobrze, że pesymistyczne oszacowanie złożoności zrówna się z optymistycznym. |
||
Jeżeli prawdopodobieństwo wystąpienia przypadku pesymistycznego w praktyce jest duże, to można skorzystać ze specjalnych algorytmów znajdowania dobrej mediany. Niestety algorytmy te mają dość dużą złożoność, dlatego w takiej sytuacji należy też rozważyć skorzystanie z innych algorytmów sortowania, takich jak np. [[sortowanie przez kopcowanie |
Jeżeli prawdopodobieństwo wystąpienia przypadku pesymistycznego w praktyce jest duże, to można skorzystać ze specjalnych algorytmów znajdowania dobrej mediany. Niestety algorytmy te mają dość dużą złożoność, dlatego w takiej sytuacji należy też rozważyć skorzystanie z innych algorytmów sortowania, takich jak np. [[sortowanie przez kopcowanie]] (ang. ''heap sort''), [[sortowanie pozycyjne]] (''radix sort''), czy [[sortowanie przez scalanie]] (''mergesort''). |
||
== Przykładowe implementacje == |
== Przykładowe implementacje == |
||
* [[b:Kody źródłowe/Sortowanie szybkie|Przykładowe implementacje sortowania szybkiego na Wikibooks]] |
|||
== Przypisy == |
|||
{{Przypisy}} |
{{Przypisy}} |
||
== Zobacz też == |
|||
* [[sortowanie]] |
|||
== Linki zewnętrzne == |
== Linki zewnętrzne == |
||
* [http://www.youtube.com/watch?v=ywWBy6J5gz8 Algorytm przedstawiony z wykorzystaniem węgierskiego tańca] |
* [http://www.youtube.com/watch?v=ywWBy6J5gz8 Algorytm przedstawiony z wykorzystaniem węgierskiego tańca] |
||
* [http://algorytmy.ency.pl/tutorial/quicksort Przykładowe wykonanie algorytmu krok po kroku] |
|||
* [https://www.toptal.com/developers/sorting-algorithms/quick-sort Animacje obrazujące szybkość algorytmu w kilku przypadkach] |
|||
{{Algorytmy sortowania}} |
{{Algorytmy sortowania}} |
||
{{SORTUJ:Szybkie sortowanie}} |
|||
[[Kategoria:Algorytmy sortowania |
[[Kategoria:Algorytmy sortowania]] |
||
[[no:Sorteringsalgoritme#Quick sort]] |
Aktualna wersja na dzień 01:08, 14 cze 2024
Rodzaj | |
---|---|
Struktura danych |
Różne |
Złożoność | |
Czasowa |
|
Pamięciowa |
zależnie od implementacji |
Sortowanie szybkie (ang. quicksort) – jeden z popularnych algorytmów sortowania działających na zasadzie „dziel i zwyciężaj”[1].
Sortowanie szybkie (ang. QuickSort) zostało wynalezione w 1962 przez C.A.R. Hoare’a[2].
Algorytm sortowania szybkiego jest wydajny: jego średnia złożoność obliczeniowa jest rzędu [1]. Ze względu na szybkość i prostotę implementacji jest powszechnie używany. Jego implementacje znajdują się w bibliotekach standardowych wielu środowisk programowania[3][4].
Algorytm
[edytuj | edytuj kod]Z tablicy wybiera się element rozdzielający, po czym tablica jest dzielona na dwa fragmenty: do początkowego przenoszone są wszystkie elementy nie większe od rozdzielającego, do końcowego wszystkie większe. Potem sortuje się osobno początkową i końcową część tablicy[1]. Rekursja kończy się, gdy kolejny fragment uzyskany z podziału zawiera pojedynczy element, jako że jednoelementowa tablica nie wymaga sortowania.
Jeśli przez l oznacza się indeks pierwszego, a przez r – ostatniego elementu sortowanego fragmentu tablicy, zaś przez i – indeks elementu, na którym tablica została podzielona, to procedurę sortowania można (w dużym uproszczeniu) przedstawić następującym pseudokodem[potrzebny przypis]:
PROCEDURE Quicksort(tablica, l, r)
BEGIN
IF l < r THEN { jeśli fragment dłuższy niż 1 element }
BEGIN
i := PodzielTablice(tablica, l, r); { podziel i zapamiętaj punkt podziału }
Quicksort(tablica, l, i-1); { posortuj lewą część }
Quicksort(tablica, i+1, r); { posortuj prawą część }
END
END
{wybiera element, który ma być użyty do podziału
i przenosi wszystkie elementy mniejsze na lewo od
tego elementu, a elementy większe lub równe, na prawo
od wybranego elementu }
PROCEDURE PodzielTablice(tablica, l, r)
BEGIN
indeksPodzialu := WybierzPunktPodzialu(l, r); {wybierz element, który posłuży do podziału tablicy}
wartoscPodzialu := tablica[indeksPodzialu]; {zapamiętaj wartość elementu}
Zamien(tablica, indeksPodzialu, r); {przenieś element podziału na koniec tablicy, aby sam nie brał udziału w podziale}
aktualnaPozycja := l;
FOR i:=l TO r-1 DO {iteruj przez wszystkie elementy, jeśli element jest mniejszy niż wartość elementu podziału dodaj go do "lewej" strony}
BEGIN
IF tablica[i] < wartoscPodzialu THEN
BEGIN
Zamien(tablica, i, aktualnaPozycja);
aktualnaPozycja := aktualnaPozycja + 1;
END
END
Zamien(tablica, aktualnaPozycja, r); {wstaw element podziału we właściwe miejsce}
return aktualnaPozycja;
END
{ podstawowa implementacja wyboru punktu podziału - wybiera element "środkowy" w tablicy }
PROCEDURE WybierzPunktPodzialu(l, r)
BEGIN
return l + (r-l) div 2;
END
{ zamienia miejscami elementy w komórkach i1, i2 }
PROCEDURE Zamien(tablica, i1, i2)
BEGIN
IF i1<>i2 THEN
BEGIN
aux := tablica[i1];
tablica[i1] := tablica[i2];
tablica[i2] := aux;
END
END
Właściwe działanie algorytmu wymaga, aby procedura PodzielTablice
pozostawiała element rozdzielający na końcu lewej części uzyskanej z podziału. Wówczas element ten znajduje się na swojej ostatecznej pozycji i nie podlega dalszemu przetwarzaniu – rekurencyjne wywołania Quicksort
nie obejmują indeksu i. Tym samym do dalszego przetwarzania przekazuje się o jeden element mniej, co gwarantuje zakończenie rekurencji.
Złożoność
[edytuj | edytuj kod]Złożoność algorytmu zależy od wyboru elementu rozdzielającego; jeśli podziały są zrównoważone algorytm jest tak szybki jak sortowanie przez scalanie, czyli w przeciwnym przypadku może działać tak wolno jak sortowanie przez wstawianie Średni czas działania przy losowym wyborze elementu rozdzielającego, dorównuje przypadkowi optymistycznemu[1].
Przypadek optymistyczny
[edytuj | edytuj kod]W przypadku optymistycznym, jeśli mamy szczęście za każdym razem wybrać medianę z sortowanego fragmentu tablicy, to liczba porównań niezbędnych do uporządkowania n-elementowej tablicy opisana jest rekurencyjnym wzorem
Dla dużych n:
co daje w rozwiązaniu liczbę porównań (a więc wskaźnik złożoności czasowej):
Równocześnie otrzymuje się minimalne zagnieżdżenie rekursji (czyli głębokość stosu, a co za tym idzie, złożoność pamięciową):
Przypadek przeciętny
[edytuj | edytuj kod]W przypadku przeciętnym, to jest dla równomiernego rozkładu prawdopodobieństwa wyboru elementu z tablicy:
złożoność jest o 39% wyższa niż w przypadku optymistycznym.
Przypadek pesymistyczny
[edytuj | edytuj kod]W przypadku pesymistycznym, jeśli zawsze wybierzemy element najmniejszy (albo największy) w sortowanym fragmencie tablicy, to:
skąd wynika kwadratowa złożoność czasowa:
W tym przypadku otrzymuje się też olbrzymią, liniową złożoność pamięciową:
Usprawnienia algorytmu
[edytuj | edytuj kod]Wybór elementu
[edytuj | edytuj kod]Najprostsza, „naiwna” metoda podziału – wybieranie zawsze skrajnego elementu tablicy – dla danych już uporządkowanych daje katastrofalną złożoność Trywialne na pozór zadanie posortowania posortowanej tablicy okazuje się dla tak zapisanego algorytmu zadaniem skrajnie trudnym. Aby uchronić się przed takim przypadkiem stosuje się najczęściej randomizację wyboru albo wybór „środkowy z trzech”. Pierwszy sposób opiera się na losowaniu elementu rozdzielającego, co sprowadza prawdopodobieństwo zajścia najgorszego przypadku do wartości zaniedbywalnie małych. Drugi sposób polega na wstępnym wyborze trzech elementów z rozpatrywanego fragmentu tablicy, i użyciu jako elementu osiowego tego z trzech, którego wartość leży pomiędzy wartościami pozostałych dwu. Można również uzupełnić algorytm o poszukiwanie przybliżonej mediany (patrz poniżej: Gwarancja złożoności).
Ograniczenie rekursji
[edytuj | edytuj kod]Wysoka wydajność algorytmu sortowania szybkiego predestynuje go do przetwarzania dużych tablic. Takie zastosowanie wymaga jednak zwrócenia szczególnej uwagi na głębokość rekursji. Głębokość rekursji wiąże się bowiem z wykorzystaniem stosu maszynowego.
W najgorszym przypadku, jeśli algorytm będzie dzielił tablicę zawsze na część jednoelementową i resztę, to rekursja osiągnie głębokość Aby temu zapobiec, należy sprawdzać, która część jest krótsza – i tę porządkować najpierw. Z dłuższą zaś nie wchodzić w rekursję, lecz ponownie dzielić na tym samym poziomie wywołania:
PROCEDURE Quicksort( l, r )
BEGIN
WHILE l < r DO { dopóki fragment dłuższy niż 1 element }
BEGIN
i := PodzielTablice( l, r );
IF (i-l) ≤ (r-i) THEN { sprawdź, czy lewa część krótsza }
BEGIN { TAK? }
Quicksort( l, i-1 ); { posortuj lewą, krótszą część }
l := i+1 { i kontynuuj dzielenie dłuższej }
END
ELSE
BEGIN { NIE }
Quicksort( i, r ); { posortuj prawą, krótszą część }
r := i-1 { i kontynuuj dzielenie dłuższej }
END
END
END
Przy takiej organizacji pracy na stosie zawsze pozostają zapamiętane (w zmiennych i, r albo l, i) indeksy ograniczające dłuższą, jeszcze nie posortowaną część tablicy, a wywołanie rekurencyjne zajmuje się częścią krótszą. To znaczy, że na każdym poziomie wywołań algorytm obsługuje fragment będący co najwyżej połową fragmentu z poprzedniego poziomu. Stąd wynika, że poziomów wywołań w najgorszym przypadku nie będzie więcej niż log2n, gdzie n oznacza długość całej tablicy. Zatem usprawnienie to zmienia asymptotyczne wykorzystanie pamięci przez algorytm w pesymistycznym przypadku z do
Quicksort w miejscu
[edytuj | edytuj kod]Istnieje modyfikacja czyniąca algorytm quicksort działającym w miejscu. W oryginalnym sortowaniu szybkim używa się rekursji lub stosu (de facto oba sposoby niewiele się różnią – rekursja w uproszczeniu jest niejawnym stosem) do zapamiętywania miejsc podziału. Więc chociaż algorytm w obu wersjach nie korzysta z dodatkowych tablic o rozmiarze zależnym od rozmiaru danych wejściowych, to nie można nazywać go działającym w miejscu, gdyż wysokość, a więc i wymagania pamięciowe wywołań rekursji/stosu są ściśle zależne od rozmiaru danych początkowych.
Załóżmy, że dla sortowanej tablicy A funkcja PodzielTablice(l,p) zwróciła wartość s. W oryginalnym algorytmie quicksort powinno zostać wykonane wywołania Quicksort(l,s-1) i Quicksort(s+1,p). Zamiast tego „zajmujemy się” tylko Quicksort(l,s-1), a pozycje s+1 i p zapamiętujemy w następujący sposób:
- s+1: jest jednoznacznie wyznaczona przez koniec ciągu (l,s-1) → (s+1) = (s-1) + 2
- p: znajdujemy maksimum ciągu (s+1,p) i zamieniamy tę pozycję z pozycją s. Aby odtworzyć pozycję p, wystarczy przeszukiwać ciąg w prawo do znalezienia elementu większego od wartości stojącej na pozycji s. Wtedy indeks elementu o najmniejszej wartości większej od A[s] to p+1.
Metoda ta sprowadza koszt pamięciowy algorytmu do wartości stałej, O(1), wymaga jednak dodatkowego nakładu czasu na wyszukiwanie maksymalnych elementów kolejno sortowanych fragmentów tablicy. Ujmuje więc algorytmowi jego główną zaletę, wpisaną nawet w jego nazwę – szybkość działania.
Drobne fragmenty
[edytuj | edytuj kod]U podstaw kolejnego usprawnienia leży spostrzeżenie, że około połowa wszystkich rekurencyjnych wywołań procedury dotyczy jednoelementowych fragmentów tablicy – a więc fragmentów z definicji posortowanych. Co więcej, po wliczeniu dodatkowej pracy potrzebnej na wybór elementu dzielącego i zorganizowanie pętli dzielącej tablicę okazuje się, że sortowanie tablic nawet kilkuelementowych algorytmem quicksort jest bardziej pracochłonne niż jakimś algorytmem prostym, na przykład przez wstawianie.
Warto więc zaniechać dalszych podziałów, gdy uzyskane fragmenty staną się dostatecznie krótkie – rzędu kilku lub kilkunastu elementów. Otrzymuje się w wyniku tablicę „prawie posortowaną”, w której większość elementów może nie znajduje się na właściwych miejscach, ale są blisko właściwych miejsc. Taką tablicę ostatecznie sortuje się algorytmem wstawiania, który bardzo efektywnie radzi sobie z tego rodzaju danymi. Jak pokazuje praktyka, wybór granicznej długości fragmentu (progu „odcięcia” rekursji, ang. cutoff) nie wymaga szczególnych rygorów – algorytm działa niemal równie dobrze dla wartości od 5 do 25. W większości zastosowań pozwala to osiągnąć oszczędność łącznego czasu wykonania rzędu 20%[5].
Gwarancja złożoności
[edytuj | edytuj kod]Pomimo wszelkich usprawnień, pozostaje jednak, zazwyczaj znikome, prawdopodobieństwo zajścia przypadku pesymistycznego, w którym złożoność czasowa wynosi Jeśli chcemy mieć pewność wykonania sortowania w czasie nie dłuższym niż należy uzupełnić algorytm o poszukiwanie przybliżonej mediany, czyli elementu dzielącego posortowaną tablicę na tyle dobrze, że pesymistyczne oszacowanie złożoności zrówna się z optymistycznym.
Jeżeli prawdopodobieństwo wystąpienia przypadku pesymistycznego w praktyce jest duże, to można skorzystać ze specjalnych algorytmów znajdowania dobrej mediany. Niestety algorytmy te mają dość dużą złożoność, dlatego w takiej sytuacji należy też rozważyć skorzystanie z innych algorytmów sortowania, takich jak np. sortowanie przez kopcowanie (ang. heap sort), sortowanie pozycyjne (radix sort), czy sortowanie przez scalanie (mergesort).
Przykładowe implementacje
[edytuj | edytuj kod]Przypisy
[edytuj | edytuj kod]- ↑ a b c d Thomas H. Cormen, Charles E. Leiserson, Ronald. R. Rivest: Wprowadzenie do algorytmów. Warszawa: Wydawnictwa Naukowo-Techniczne, 1997, 1998, s. 186–205. ISBN 83-204-2317-1.
- ↑ C.A.R. Hoare: Quicksort. Computer Journal, Vol. 5, 1, 10–15 (1962).
- ↑ Uwaga dot. implementacji algorytmu Quicksort w funkcji
sort()
języka PHP: PHP: sort - Manual. [dostęp 2014-03-28]. (ang.). - ↑ Opis funkcji
qsort
z biblioteki standardowej języka C++: qsort - C++ Reference. [dostęp 2014-03-28]. (ang.). - ↑ Jon Bentley: Perełki oprogramowania. tłum. Agata Tomaszewska. Wyd. 2. Warszawa: WNT, 2001, s. 151, 277, seria: Klasyka Informatyki. ISBN 83-204-2627-8.