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	${\displaystyle O(1)}$

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

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

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

${\displaystyle {\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 ${\displaystyle (a_{1},a_{6},a_{11}),}$ ${\displaystyle (a_{2},a_{7},a_{12}),}$ ${\displaystyle (a_{3},a_{8}),}$ ${\displaystyle (a_{4},a_{9}),(a_{5},a_{10}).}$ Na przykład fragment ${\displaystyle (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 ${\displaystyle (a_{1},a_{4},a_{7},a_{10}),}$ ${\displaystyle (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 ${\displaystyle (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

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 ${\displaystyle 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 ${\displaystyle N.}$

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

Jeśli ${\displaystyle N}$ jest potęgą dwójki, to sortowanie z oryginalnym ciągiem odstępów zaproponowanym przez Shella wykonuje w najgorszym przypadku ${\displaystyle \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 ${\displaystyle 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 ${\displaystyle h_{k}=\lfloor 2{,}25h_{k-1}\rfloor .}$

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

Złożoność obliczeniowa

Zachodzi intrygująca własność: po ${\displaystyle h_{2}}$-sortowaniu dowolnej ${\displaystyle h_{1}}$-posortowanej tablicy pozostaje ona nadal ${\displaystyle h_{1}}$-posortowana^[12]. Każda ${\displaystyle h_{1}}$-posortowana i ${\displaystyle h_{2}}$-posortowana tablica jest też ${\displaystyle (a_{1}h_{1}+a_{2}h_{2})}$-posortowana dla wszystkich całkowitych nieujemnych ${\displaystyle a_{1}}$ i ${\displaystyle a_{2}.}$ Zatem złożoność pesymistyczna sortowania Shella wiąże się z problemem Frobeniusa: dla danych całkowitych ${\displaystyle h_{1},\dots ,h_{n}}$ o ${\displaystyle nwd=1}$ liczba Frobeniusa ${\displaystyle g(h_{1},\dots ,h_{n})}$ to największa liczba całkowita, której nie da się przedstawić w postaci ${\displaystyle a_{1}h_{1}+\ldots +a_{n}h_{n}}$ przy ${\displaystyle 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 ${\displaystyle 0{,}5349N{\sqrt {N}}-0{,}4387N-0{,}097{\sqrt {N}}+O(1)}$^[13]. Knuth wyznaczył średnią złożoność sortowania ${\displaystyle N}$-elementowej tablicy z dwoma przebiegami ${\displaystyle (h,1)}$ jako ${\displaystyle 2N^{2}/h+{\sqrt {\pi N^{3}h}}}$^[6]. Wynika stąd, że dwuprzebiegowe sortowanie Shella z ${\displaystyle h=\Theta (N^{1/3})}$ wykonuje średnio ${\displaystyle 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 ${\displaystyle (ch,cg,1),}$ gdzie ${\displaystyle h}$ i ${\displaystyle g}$ są względnie pierwsze wynosi ${\displaystyle {\frac {N^{2}}{4ch}}+O(N)}$ w pierwszym przebiegu, ${\displaystyle {\frac {1}{8g}}{\sqrt {\frac {\pi }{ch}}}(h-1)N^{3/2}+O(hN)}$ w drugim przebiegu i ${\displaystyle \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 ${\displaystyle \Psi (h,g)}$ z ostatniego wzoru jest asymptotycznie równa ${\displaystyle {\sqrt {\frac {\pi h}{128}}}g+O(g^{-1/2}h^{1/2})+O(gh^{-1/2}).}$ W szczególności, gdy ${\displaystyle h=\Theta (N^{7/15}),}$ a ${\displaystyle g=\Theta (h^{1/5}),}$ średni czas sortowania jest rzędu ${\displaystyle 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 ${\displaystyle O(N^{5/4})}$^[6], a z ciągiem Gonneta i Baezy-Yatesa wykonuje średnio ${\displaystyle 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 ${\displaystyle \log _{2}N!,}$ przy czym do ciągu 1, 4, 10, 23, 57, 132, 301, 701 dodano dalsze wyrazy zgodnie ze wzorem ${\displaystyle 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 ${\displaystyle m}$-przebiegowym sortowaniu Shella: ${\displaystyle \Omega (mN^{1+1/m})}$ przy ${\displaystyle m\leqslant \log _{2}N}$ i ${\displaystyle \Omega (mN)}$ przy ${\displaystyle m>\log _{2}N}$^[16]. Zatem algorytm ten ma szanse działać w średnim czasie rosnącym asymptotycznie jak ${\displaystyle 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 ${\displaystyle \Omega (N(\log N/\log \log N)^{2})}$^[17].

Zastosowania

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ż

• sortowanie grzebieniowe

Przypisy

Bibliografia

• 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

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