Sortowanie Shella

Sortowanie Shella
	; 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

Sortowanie Shella (ang. Shellsort) – jeden z algorytmów sortowania działających w miejscu i korzystających z porównań elementów. Można go traktować jako uogólnienie sortowania przez wstawianie lub sortowania bąbelkowego, dopuszczające porównania i zamiany elementów położonych daleko od siebie. Na początku sortuje on elementy tablicy położone daleko od siebie, a następnie stopniowo zmniejsza odstępy między sortowanymi elementami. Dzięki temu może je przenieść w docelowe położenie szybciej niż zwykłe sortowanie przez wstawianie.

Pierwszą wersję tego algorytmu, której zawdzięcza on swoją nazwę, 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

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}{rc}&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 $(a_{1},a_{6},a_{11}),$ $(a_{2},a_{7},a_{12}),$ $(a_{3},a_{8}),$ $(a_{4},a_{9}),(a_{5},a_{10}).$ Na przykład fragment $(a_{1},a_{6},a_{11})$ zmienia z (62, 17, 25) na (17, 25, 62).

Następny przebieg, czyli 3-sortowanie, sortuje przez wstawianie zawartość fragmentów $(a_{1},a_{4},a_{7},a_{10}),$ $(a_{2},a_{5},a_{8},a_{11}),(a_{3},a_{6},a_{9},a_{12}).$

Ostatni przebieg, czyli 1-sortowanie, to zwykłe sortowanie przez wstawianie całej tablicy $(a_{1},\dots ,a_{12}).$

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

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\geqslant 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 ,\dots ,1$	$\Theta (N^{2})$ [gdy $N=2^{p}$ ]	Shell, 1959^[1]
$2\lfloor N/2^{k+1}\rfloor +1$	$2\left\lfloor {\frac {N}{4}}\right\rfloor +1,\dots ,3,1$	$\Theta (N^{3/2})$	Frank, Lazarus, 1960^[2]
$2^{k}-1$	$1,3,7,15,31,63,\dots$	$\Theta (N^{3/2})$	Hibbard, 1963^[3]
$2^{k}+1,$ na początku 1	$1,3,5,9,17,33,65,\dots$	$\Theta (N^{3/2})$	Papiernow, Stasiewicz, 1965^[4]
kolejne liczby postaci $2^{p}3^{q}$	$1,2,3,4,6,8,9,12,\dots$	$\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,\dots$	$\Theta (N^{3/2})$	Knuth, 1973^[6]
$\prod \limits _{0\leqslant q<r \atop 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} :n\geqslant (5/2)^{q+1},$ $\forall p:0\leqslant p<q\Rightarrow \gcd(a_{p},n)=1\}$	$1,3,7,21,48,112,\dots$	$O\left(N^{1+{\sqrt {\frac {8\ln \left(5/2\right)}{\ln(N)}}}}\right)$	Incerpi, Sedgewick, 1985^[7]
$4^{k}+3\cdot 2^{k-1}+1,$ na początku 1	$1,8,23,77,281,\dots$	$O(N^{4/3})$	Sedgewick, 1986^[8]
$9(4^{k-1}-2^{k-1})+1,4^{k+1}-6\cdot 2^{k}+1$	$1,5,19,41,109,\dots$	$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 ,\dots ,1$	?	Gonnet, Baeza-Yates, 1991^[9]
$\left\lceil 1{,}8\cdot 2{,}25^{k-1}-0{,}8\right\rceil$	$1,4,9,20,46,103,\dots$	?	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 $\Theta (N^{2})$ 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(N\log N),$ 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{,}25h_{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{,}25h'_{k-1}+1,$ $h'_{1}=1.$

Złożoność obliczeniowa edytuj

Zachodzi intrygująca własność: po $h_{2}$ -sortowaniu dowolnej $h_{1}$ -posortowanej tablicy pozostaje ona nadal $h_{1}$ -posortowana^[12]. Każda $h_{1}$ -posortowana i $h_{2}$ -posortowana tablica jest też $(a_{1}h_{1}+a_{2}h_{2})$ -posortowana dla wszystkich całkowitych nieujemnych $a_{1}$ i $a_{2}.$ Zatem złożoność pesymistyczna sortowania Shella wiąże się z problemem Frobeniusa: dla danych całkowitych $h_{1},\dots ,h_{n}$ o $nwd=1$ liczba Frobeniusa $g(h_{1},\dots ,h_{n})$ to największa liczba całkowita, której nie da się przedstawić w postaci $a_{1}h_{1}+\ldots +a_{n}h_{n}$ przy $a_{1},\dots ,a_{n}$ 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=\Theta (N^{1/3})$ wykonuje średnio $O(N^{5/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^{2}g^{3}h^{2})$ w trzecim przebiegu. Skomplikowana funkcja $\Psi (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=\Theta (N^{7/15}),$ a $g=\Theta (h^{1/5}),$ średni czas sortowania jest rzędu $O(N^{23/15}).$

Na podstawie doświadczeń odgadnięto, że z ciągami Hibbarda i Knutha algorytm działa w średnim czasie rzędu $O(N^{5/4})$ ^[6], a z ciągiem Gonneta i Baezy-Yatesa wykonuje średnio $0{,}41N\ln N(\ln \ln N+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 $\log _{2}N!,$ przy czym do ciągu 1, 4, 10, 23, 57, 132, 301, 701 dodano dalsze wyrazy zgodnie ze wzorem $h_{k}=\lfloor 2{,}25h_{k-1}\rfloor .$

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: $\Omega (mN^{1+1/m})$ przy $m\leqslant \log _{2}N$ i $\Omega (mN)$ przy $m>\log _{2}N$ ^[16]. Zatem algorytm ten ma szanse działać w średnim czasie rosnącym asymptotycznie jak $N\log N$ 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 $\Omega (N(\log N/\log \log N)^{2})$ ^[17].

Zastosowania edytuj

Sortowanie Shella wykonuje 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 była w jądrze systemu operacyjnego Linux^[19] do 2017 roku^[20].

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^[21].

Zobacz też edytuj

sortowanie grzebieniowe

Przypisy edytuj

↑ ^a ^b D.L. Shell. A High-Speed Sorting Procedure. „Communications of the ACM”. 2 (7), s. 30–32, 1959. DOI: 10.1145/368370.368387.
↑ 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.
↑ 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.
↑ А.А. Папернов, Г.В. Стасевич. Об одном методе упорядочивания информации в запоминающих устройствах цифровых машин. „Проблемы передачи информации”. 1 (3), s. 81–98, 1965. (ros.).
↑ Vaughan Ronald Pratt: Shellsort and Sorting Networks (Outstanding Dissertations in the Computer Sciences). Garland, 1979. ISBN 0-824-04406-1.
↑ ^a ^b ^c 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.
↑ Janet Incerpi, Robert Sedgewick. Improved Upper Bounds on Shellsort. „Journal of Computer and System Sciences”. 31 (2), s. 210–224, 1985.
↑ ^a ^b 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.
↑ ^a ^b 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.
↑ 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.
↑ 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.
↑ 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.
↑ Terje O. Espelid. Analysis of a Shellsort Algorithm. „BIT Numerical Mathematics”. 13 (4), s. 394–400, 1973. DOI: 10.1007/BF01933401.
↑ 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.
↑ Svante Janson, Donald E. Knuth. Shellsort with Three Increments. „Random Structures and Algorithms”. 10 (1–2), s. 125–142, 1997. arXiv:cs/9608105.
↑ 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.
↑ C. Greg Plaxton, Bjorn Poonen, Torsten Suel. Improved Lower Bounds for Shellsort. „Annual Symposium on Foundations of Computer Science”. 33, s. 226–235, 1992.
↑ Manuel Novoa III: libc/stdlib/stdlib.c. [dostęp 2011-03-30].
↑ kernel/groups.c. [dostęp 2012-02-06].
↑ kernel/git/torvalds/linux.git – Linux kernel source tree [online], git.kernel.org [dostęp 2020-11-14] .
↑ Julian Seward: bzip2/blocksort.c. [dostęp 2011-03-30].

Bibliografia edytuj

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.
Analysis of Shellsort and Related Algorithms, Robert Sedgewick, Fourth European Symposium on Algorithms, Barcelona, wrzesień 1996.
O sortowaniu Shella. sun.aei.polsl.pl. [zarchiwizowane z tego adresu (2016-11-28)]., Marcin Ciura, Delta, listopad 2008.

Linki zewnętrzne edytuj

Sortowanie Shella z odstępami 5, 3, 1 przedstawione jako węgierski taniec

[Shell-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.

[Knuth-6] 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.

[Sedgewick-8] 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.

[Gonnet-9] 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. arXiv:cs/9608105.

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

[17] C. Greg Plaxton, Bjorn Poonen, Torsten Suel. Improved Lower Bounds for Shellsort. „Annual Symposium on Foundations of Computer Science”. 33, s. 226–235, 1992.

[18] Manuel Novoa III: libc/stdlib/stdlib.c. [dostęp 2011-03-30].

[19] rnel/groups.c. [dostęp 2012-02-06].

[20] kernel/git/torvalds/linux.git – Linux kernel source tree [online], git.kernel.org [dostęp 2020-11-14] .

[21] Julian Seward: bzip2/blocksort.c. [dostęp 2011-03-30].

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

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