Sortowanie Shella

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania
Sortowanie Shella
Sorting shellsort anim.gif
Przykład działania sortowania Shella z odstępami 23, 10, 4, 1
Rodzaj Sortowanie
Struktura danych Tablica
Złożoność
Czasowa zależy od ciągu odstępów
Pamięciowa O(1)

Sortowanie Shella (ang. Shellsort) – algorytm sortowania działający w miejscu i korzystający z porównań elementów. Stanowi uogólnienie sortowania przez wstawianie, dopuszczające porównania i zamiany elementów położonych daleko od siebie. Jego pierwszą wersję opublikował w 1959 roku Donald Shell[1].

Złożoność czasowa sortowania Shella w dużej mierze zależy od użytego w nim ciągu odstępów. Wyznaczenie jej dla wielu stosowanych w praktyce wariantów tego algorytmu pozostaje problemem otwartym.

Opis algorytmu[edytuj | edytuj kod]

Sortowanie Shella to algorytm wieloprzebiegowy. Kolejne przebiegi polegają na sortowaniu przez proste wstawianie elementów oddalonych o ustaloną liczbę miejsc h, czyli tak zwanym h-sortowaniu.

Poniżej zilustrowano sortowanie przykładowej tablicy metodą Shella z odstępami 5, 3, 1.


\begin{array}{rcccccccccccc}
    &a_1&a_2&a_3&a_4&a_5&a_6&a_7&a_8&a_9&a_{10}&a_{11}&a_{12}\\
  \hbox{dane wejściowe:}
    & 62& 83& 18& 53& 07& 17& 95& 86& 47& 69& 25& 28\\
  \hbox{po 5-sortowaniu:}
    & 17& 28& 18& 47& 07& 25& 83& 86& 53& 69& 62& 95\\
  \hbox{po 3-sortowaniu:}
    & 17& 07& 18& 47& 28& 25& 69& 62& 53& 83& 86& 95\\
  \hbox{po 1-sortowaniu:}
    & 07& 17& 18& 25& 28& 47& 53& 62& 69& 83& 86& 95\\
\end{array}

Pierwszy przebieg, czyli 5-sortowanie, sortuje osobno przez wstawianie zawartość każdego z fragmentów (a1, a6, a11), (a2, a7, a12), (a3, a8), (a4, a9), (a5, a10). Na przykład fragment (a1, a6, a11) zmienia z (62, 17, 25) na (17, 25, 62).

Następny przebieg, czyli 3-sortowanie, sortuje przez wstawianie zawartość fragmentów (a1, a4, a7, a10), (a2, a5, a8, a11), (a3, a6, a9, a12).

Ostatni przebieg, czyli 1-sortowanie, to zwykłe sortowanie przez wstawianie całej tablicy (a1,..., a12).

Jak widać, fragmenty tablicy, na których operuje algorytm Shella, są z początku krótkie, a pod koniec dłuższe, ale prawie uporządkowane. W obu tych przypadkach sortowanie przez proste wstawianie działa wydajnie.

Sortowanie Shella nie jest stabilne, czyli może nie zachowywać wejściowej kolejności elementów o równych kluczach. Wykazuje ono zachowanie naturalne, czyli krótszy czas sortowania dla częściowo uporządkowanych danych wejściowych.

Ciągi odstępów[edytuj | edytuj kod]

Każdy ciąg odstępów zakończony jedynką prowadzi do poprawnie sortującego algorytmu. Własności tak otrzymanych wersji algorytmu mogą być jednak bardzo różne.

W poniższej tabeli zestawiono większość dotychczas opublikowanych propozycji ciągów odstępów. Niektóre z tych ciągów mają malejące wyrazy zależne od N, czyli rozmiaru sortowanej tablicy. Inne to rosnące ciągi nieskończone, z których należy użyć w odwrotnej kolejności wyrazów mniejszych od N.

Wyraz ogólny ciągu (k ≥ 1) Konkretne odstępy Rząd złożoności
pesymistycznej
Autor i rok publikacji
\lfloor N / 2^k \rfloor \left\lfloor\frac{N}{2}\right\rfloor,
        \left\lfloor\frac{N}{4}\right\rfloor, \ldots, 1 \Theta(N^2) [gdy N=2p] Shell, 1959[1]
2 \lfloor N / 2^{k+1} \rfloor + 1 2 \left\lfloor\frac{N}{4}\right\rfloor + 1, \ldots, 3, 1 \Theta(N^{3/2}) Frank, Lazarus, 1960[2]
2^k - 1 1, 3, 7, 15, 31, 63, \ldots \Theta(N^{3/2}) Hibbard, 1963[3]
2^k + 1, na początku 1 1, 3, 5, 9, 17, 33, 65, \ldots \Theta(N^{3/2}) Papiernow, Stasiewicz, 1965[4]
kolejne liczby postaci 2^p 3^q 1, 2, 3, 4, 6, 8, 9, 12, \ldots \Theta(N \log^2 N) Pratt, 1971[5]
(3^k - 1) / 2, nie większe niż \lceil N / 3 \rceil 1, 4, 13, 40, 121, \ldots \Theta(N^{3/2}) Knuth, 1973[6]
\prod
  \limits_{\scriptscriptstyle 0\le q<r\atop
           \scriptscriptstyle q\neq(r^2+r)/2-k}a_q, \hbox{gdzie}
r = \left\lfloor \sqrt{2k+\sqrt{2k}} \right\rfloor,
a_q=\min\{n\in\mathbb{N}\colon n\ge(5/2)^{q+1},
\forall p\colon0\le p<q\Rightarrow\gcd(a_p,n)=1\}
1, 3, 7, 21, 48, 112, \ldots O(N e^\sqrt{8\ln(5/2)\ln N}) Incerpi, Sedgewick, 1985[7]
4^k + 3\cdot2^{k-1} + 1, na początku 1 1, 8, 23, 77, 281, \ldots O(N^{4/3}) Sedgewick, 1986[8]
9(4^{k-1}-2^{k-1})+1, 4^{k+1}-6\cdot2^k+1 1, 5, 19, 41, 109, \ldots O(N^{4/3}) Sedgewick, 1986[8]
h_k = \max\left\{\left\lfloor 5h_{k-1}/11 \right\rfloor, 1\right\}, h_0 = N \left\lfloor \frac{5N}{11} \right\rfloor, \left\lfloor \frac{5}{11}\left\lfloor \frac{5N}{11} \right\rfloor\right\rfloor, \ldots, 1  ? Gonnet, Baeza-Yates, 1991[9]
\left\lceil \frac{9^k-4^k}{5\cdot4^{k-1}} \right\rceil 1, 4, 9, 20, 46, 103, \ldots  ? Tokuda, 1992[10]
nieznany 1, 4, 10, 23, 57, 132, 301, 701  ? Ciura, 2001[11]

Jeśli N jest potęgą dwójki, to sortowanie z oryginalnym ciągiem odstępów zaproponowanym przez Shella wykonuje w najgorszym przypadku Θ(N2) porównań. Przypadek ten zachodzi na przykład wtedy, gdy elementy większe i mniejsze od mediany zajmują odpowiednio parzyste i nieparzyste pozycje tablicy, ponieważ są one porównywane dopiero w ostatnim przebiegu.

Wersja zaproponowana przez Pratta ma wprawdzie wyższą złożoność niż optymalne dla algorytmów sortowania opartych na porównaniach O(NlogN), ale za to prowadzi do sieci sortującej o liczbie komparatorów tego samego rzędu, co sieć Batchera.

Zauważono, że średnio najmniej porównań elementów potrzeba, gdy ilorazy kolejnych odstępów leżą mniej więcej pomiędzy 2,2 a 2,3. Dlatego ciągi Gonneta i Baezy-Yatesa o ilorazie 2,2 i Tokudy o ilorazie 2,25 sprawdzają się w praktyce. Nie wiadomo jednak, dlaczego minimum przypada właśnie w tym miejscu. Zalecane jest też stosowanie odstępów o niskich największych wspólnych dzielnikach lub zgoła parami względnie pierwszych.

Pod względem średniej liczby porównań elementów najlepsze znane ciągi odstępów to ciąg 1, 4, 10, 23, 57, 132, 301, 701 i podobne, o wyrazach znalezionych doświadczalnie. Dalsze wyrazy optymalnych ciągów pozostają nieznane. Do dobrych wyników prowadzi przedłużenie ich zgodnie ze wzorem rekurencyjnym h_k = \lfloor 2{,}25 h_{k-1} \rfloor.

Do zastosowań praktycznych można też polecić ciąg Tokudy, określony prostymi wzorami h_k = \lceil h'_k \rceil, gdzie h'_k = 2{,}25 h'_{k-1} + 1, h'_1 = 1.

Złożoność obliczeniowa[edytuj | edytuj kod]

Zachodzi intrygująca własność: po h2-sortowaniu dowolnej h1-posortowanej tablicy pozostaje ona nadal h1-posortowana[12]. Każda h1-posortowana i h2-posortowana tablica jest też (a1h1+a2h2)-posortowana dla wszystkich całkowitych nieujemnych a1 i a2. Zatem złożoność pesymistyczna sortowania Shella wiąże się z problemem Frobeniusa: dla danych całkowitych h1,..., hn o nwd = 1 liczba Frobeniusa g(h1,..., hn) to największa liczba całkowita, której nie da się przedstawić w postaci a1h1+ ... +anhn przy a1,..., an całkowitych nieujemnych. Korzystając ze wzorów na liczby Frobeniusa, potrafimy wyznaczać złożoność pesymistyczną dla kilku klas ciągów odstępów. Dowiedzione przypadki zamieszczono w powyższej tabeli.

Żaden dowiedziony wynik na temat średniej liczby operacji nie dotyczy praktycznego ciągu odstępów. Espelid wyliczył ją dla odstępów będących potęgami dwójki jako 0{,}5349N\sqrt{N}-0{,}4387N-0{,}097\sqrt{N}+O(1)[13]. Knuth wyznaczył średnią złożoność sortowania N-elementowej tablicy z dwoma przebiegami (h, 1) jako 2N^2/h + \sqrt{\pi N^3 h}[6]. Wynika stąd, że dwuprzebiegowe sortowanie Shella z h = Θ(N1/3) wykonuje średnio O(N5/3) porównań. Yao znalazł średnią złożoność sortowania z trzema przebiegami[14]. Jego wynik uściślili potem Janson i Knuth[15]. Średnia liczba porównań wykonywanych podczas sortowania z trzema przebiegami (ch, cg, 1), gdzie h i g są względnie pierwsze wynosi \frac{N^2}{4ch}+O(N) w pierwszym przebiegu, \frac{1}{8g}\sqrt{\frac{\pi}{ch}}(h-1)N^{3/2}+O(hN) w drugim przebiegu i \psi(h, g)N + \frac{1}{8}\sqrt{\frac{\pi}{c}}(c-1)N^{3/2}+O((c-1)gh^{1/2}N) + O(c^2g^3h^2) w trzecim przebiegu. Skomplikowana funkcja ψ(h, g) z ostatniego wzoru jest asymptotycznie równa \sqrt{\frac{\pi h}{128}}g + O(g^{-1/2}h^{1/2}) + O(gh^{-1/2}). W szczególności, gdy h = Θ(N7/15), a g = Θ(h1/5), średni czas sortowania jest rzędu O(N23/15).

Na podstawie doświadczeń odgadnięto, że z ciągami Hibbarda i Knutha algorytm działa w średnim czasie rzędu O(N5/4)[6], a z ciągiem Gonneta i Baezy-Yatesa wykonuje średnio 0,41NlnN(ln lnN+1/6) przesunięć elementów[9]. Aproksymacje średniej liczby operacji czynione kiedyś dla innych ciągów zawodzą, gdy sortowane tablice liczą miliony elementów.

Poniższy wykres przedstawia średnią liczbę porównań elementów w różnych wariantach sortowania Shella, dzieloną przez teoretyczne minimum, czyli log2N!, przy czym do ciągu 1, 4, 10, 23, 57, 132, 301, 701 dodano dalsze wyrazy zgodnie ze wzorem h_k = \lfloor2{,}25 h_{k-1}\rfloor.

Shell sort average number of comparisons (Polish).svg

Korzystając z teorii złożoności Kołmogorowa, Jiang, Li i Vitányi udowodnili następujące dolne ograniczenia na rząd średniej liczby operacji w m-przebiegowym sortowaniu Shella: Ω(mN1+1/m) przy m≤log2N i Ω(mN) przy m>log2N[16]. Zatem algorytm ten ma szanse działać w średnim czasie rosnącym asymptotycznie jak NlogN tylko z ciągami o liczbie odstępów rosnącej proporcjonalnie do logarytmu długości sortowanych tablic. Nie wiadomo jednak, czy sortowanie Shella może osiągnąć taki asymptotyczny rząd złożoności średniej, optymalny dla sortowań opartych na porównaniach.

Złożoność pesymistyczna dowolnej wersji sortowania Shella jest wyższego rzędu: Plaxton, Poonen i Suel wykazali, że rośnie ona co najmniej jak Ω(N(logN/log logN)2)[17].

Zastosowania[edytuj | edytuj kod]

Z sortowania Shella rzadko się obecnie korzysta w poważnych zastosowaniach. Wykonuje ono więcej działań niż sortowanie szybkie, ponadto częściej od niego nie trafia w pamięć podręczną procesora przy odczytach z pamięci.

Ze względu na stosunkowo krótki kod i nieużywanie stosu bywa ono stosowane zamiast sortowania szybkiego w implementacjach funkcji qsort z biblioteki standardowej języka C przeznaczonych dla systemów wbudowanych. Używa go na przykład biblioteka uClibc[18]. Z podobnych przyczyn implementacja sortowania Shella znalazła się w jądrze systemu operacyjnego Linux[19].

Można też stosować sortowanie Shella jako podalgorytm sortowania introspektywnego używany do sortowania krótkich podtablic, a także gdy głębokość rekurencji przekroczy zadany limit, aby zapobiec patologicznemu spowolnieniu sortowania. Działa tak na przykład bzip2, jeden z programów do kompresji danych[20].

Zobacz też[edytuj | edytuj kod]

Przypisy

  1. 1,0 1,1 D.L. Shell. A High-Speed Sorting Procedure. „Communications of the ACM”. 2 (7), s. 30–32, 1959. doi:10.1145/368370.368387. 
  2. R.M. Frank, R.B. Lazarus. A High-Speed Sorting Procedure. „Communications of the ACM”. 3 (1), s. 20-22, 1960. doi:10.1145/366947.366957. 
  3. Thomas N. Hibbard. An Empirical Study of Minimal Storage Sorting. „Communications of the ACM”. 6 (5), s. 206-213, 1963. doi:10.1145/366552.366557. 
  4. А. А. Папернов, Г. В. Стасевич. Об одном методе упорядочивания информации в запоминающих устройствах цифровых машин. „Проблемы передачи информации”. 1 (3), s. 81-98, 1965 (ros.). 
  5. Vaughan Ronald Pratt: Shellsort and Sorting Networks (Outstanding Dissertations in the Computer Sciences). Garland, 1979. ISBN 0-824-04406-1.
  6. 6,0 6,1 6,2 Metoda Shella. W: Donald E. Knuth: Sztuka programowania. Wyd. 1. T. 3: Sortowanie i wyszukiwanie. WNT, 2002, s. 87-99. ISBN 83-204-2554-9.
  7. Janet Incerpi, Robert Sedgewick. Improved Upper Bounds on Shellsort. „Journal of Computer and System Sciences”. 31 (2), s. 210-224, 1985. 
  8. 8,0 8,1 Robert Sedgewick. A New Upper Bound for Shellsort. „Journal of Algorithms”. 7 (2), s. 159-173, 1986. doi:10.1016/0196-6774(86)90001-5. 
  9. 9,0 9,1 Shellsort. W: Gaston H. Gonnet, Ricardo Baeza-Yates: Handbook of Algorithms and Data Structures: In Pascal and C. Wyd. 2. Reading, Massachusetts: Addison-Wesley, 1991, s. 161-163. ISBN 0-201-41607-7.
  10. Naoyuki Tokuda: An Improved Shellsort. W: Jan van Leeuven: Proceedings of the IFIP 12th World Computer Congress on Algorithms, Software, Architecture. Amsterdam: North-Holland Publishing Co., 1992, s. 449-457. ISBN 0-444-89747-X.
  11. Marcin Ciura: Best Increments for the Average Case of Shellsort. W: Rusins Freiwalds: Proceedings of the 13th International Symposium on Fundamentals of Computation Theory. London: Springer-Verlag, 2001, s. 106-117. ISBN 3-540-42487-3.
  12. David Gale, Richard M. Karp. A Phenomenon in the Theory of Sorting. „Journal of Computer and System Sciences”. 6 (2), s. 103-115, 1972. doi:10.1016/S0022-0000(72)80016-3. 
  13. Terje O. Espelid. Analysis of a Shellsort Algorithm. „BIT Numerical Mathematics”. 13 (4), s. 394-400, 1973. doi:10.1007/BF01933401. 
  14. Andrew Chi-Chih Yao. An Analysis of (h, k, 1)-Shellsort. „Journal of Algorithms”. 1 (1), s. 14-50, 1980. doi:10.1016/0196-6774(80)90003-6. 
  15. Svante Janson, Donald E. Knuth. Shellsort with Three Increments. „Random Structures and Algorithms”. 10 (1-2), s. 125-142, 1997. doi:10.1.1.54.9911. 
  16. Tao Jiang, Ming Li, Paul Vitányi. A Lower Bound on the Average-Case Complexity of Shellsort. „Journal of the ACM”. 47 (5), s. 905-911, 2000. doi:10.1.1.6.6508. 
  17. C. Greg Plaxton, Bjarne Poonen, Torsten Suel. Improved Lower Bounds for Shellsort. „Annual Symposium on Foundations of Computer Science”. 33, s. 226-235, 1992. doi:10.1.1.43.1393. 
  18. Manuel Novoa III: libc/stdlib/stdlib.c. [dostęp 2011-03-30].
  19. kernel/groups.c. [dostęp 2012-02-06].
  20. Julian Seward: bzip2/blocksort.c. [dostęp 2011-03-30].

Bibliografia[edytuj | edytuj kod]

Linki zewnętrzne[edytuj | edytuj kod]