Shellsort - Shellsort - Wikipedia

Shellsort

Shellsort s mezerami 23, 10, 4, 1 v akci
Třída	Algoritmus řazení
Datová struktura	Pole
Nejhorší případ výkon	Ó(n2) (nejhorší známá nejhorší sekvence mezery) Ó(n log2n) (nejznámější sekvence mezery v nejhorším případě)[1]
Nejlepší případ výkon	Ó(n log n) (většina sekvencí mezer) Ó(n log2n) (nejznámější posloupnost nejhorších případů mezery)[2]
Průměrný výkon	záleží na sekvenci mezer
Nejhorší případ složitost prostoru	О (n) celkem, O (1) pomocný

Zaměňujte páry položek v postupných krocích Shellsortu s mezerami 5, 3, 1

Shellsort, také známý jako Třídění skořápky nebo Shellova metoda, je na místě porovnání řazení. Lze na ni pohlížet jako na zevšeobecnění třídění výměnou (třídění bublin ) nebo třídění vložením (třídění vložení ).^[3] Metoda začíná tříděním dvojic prvků daleko od sebe, poté postupně zmenšuje mezeru mezi prvky, které mají být porovnávány. Začíná-li od sebe daleko od sebe, může přesunout některé nepřiměřené prvky do pozice rychleji než jednoduchá výměna nejbližšího souseda. Donald Shell zveřejnil první verzi tohoto druhu v roce 1959.^[4][5] Doba běhu Shellsortu silně závisí na sekvenci mezer, kterou používá. U mnoha praktických variant je určování jejich časová složitost zůstává otevřený problém.

Popis

Shellsort je optimalizace třídění vložení který umožňuje výměnu předmětů, které jsou od sebe daleko. Myšlenkou je uspořádat seznam prvků tak, aby počínaje kdekoli a kdekoli htento prvek vytvoří seřazený seznam. Takový seznam se říká h-tříděné. Lze to také považovat za h prokládané seznamy, každý jednotlivě seřazený.^[6] Počínaje velkými hodnotami h umožňuje prvkům pohybovat se na dlouhé vzdálenosti v původním seznamu, rychle snižuje velké množství nepořádku a ponechává méně práce menším h-tříděné kroky.^[7] Pokud je tedy seznam k-tříděno pro nějaké menší celé číslo k, pak seznam zůstane h-tříděné. V návaznosti na tuto myšlenku pro klesající posloupnost h je zaručeno, že hodnoty končící na 1 nakonec ponechají seřazený seznam.^[6]

Zjednodušeně to znamená, že pokud máme pole 1024 čísel, naše první mezera (h) může být 512. Poté projdeme seznamem porovnávajícím každý prvek v první polovině s prvkem ve druhé polovině. Naše druhá mezera (k) je 256, což rozděluje pole na čtyři sekce (počínaje 0,256 512 768) a my se ujistíme, že první položky v každé sekci jsou vzájemně seřazeny, pak druhá položka v každé sekci atd. V praxi může být sekvence mezery cokoli, ale poslední mezera je vždy 1 k dokončení třídění (účinně končící běžným vkládáním).

Níže je uveden příklad běhu Shellsortu s mezerami 5, 3 a 1.

První průchod, 5-třídění, provádí třídění vložení na pěti samostatných podskupinách (A₁, A₆, A₁₁), (A₂, A₇, A₁₂), (A₃, A₈), (A₄, A₉), (A₅, A₁₀). Například změní podadresář (A₁, A₆, A₁₁) od (62, 17, 25) do (17, 25, 62). Další průchod, třídění, provede třídění vložení na třech dílčích polích (A₁, A₄, A₇, A₁₀), (A₂, A₅, A₈, A₁₁), (A₃, A₆, A₉, A₁₂). Poslední průchod, 1-třídění, je běžný druh vložení celého pole (A₁,..., A₁₂).

Jak ilustruje příklad, subarrays, na kterých pracuje Shellsort, jsou zpočátku krátké; později jsou delší, ale téměř objednané. V obou případech funguje řazení efektivně.

Shellsort není stabilní: může změnit relativní pořadí prvků se stejnými hodnotami. Je to algoritmus adaptivního třídění v tom, že se provádí rychleji, když je vstup částečně tříděn.

Pseudo kód

Pomocí mezerové sekvence Marcina Ciury s vnitřním druhem vložení.

# Seřadit pole a [0 ... n-1].mezery = [701, 301, 132, 57, 23, 10, 4, 1]# Začněte s největší mezerou a snižte se na mezeru 1pro každého (mezera v mezery){    # Udělejte pro tuto velikost mezery třídění vložení s mezerou.    # První prvky mezery a [0..gap-1] jsou již v pořadí mezer    # přidávejte ještě jeden prvek, dokud nebude celé pole roztříděno podle mezer    pro (i = mezera; i < n; i += 1)    {        # přidat [i] k prvkům, které byly roztříděny podle mezer        # uložit [i] do temp a udělat díru na pozici i        tepl = A[i]        # posunout dřívější prvky seřazené podle mezery nahoru, dokud nenajdete správné umístění pro [i]        pro (j = i; j >= mezera a A[j - mezera] > tepl; j -= mezera)        {            A[j] = A[j - mezera]        }        # vložte temp (originál a [i]) na správné místo        A[j] = tepl    }}

Sekvence mezer

Otázka rozhodování, kterou sekvenci mezer použít, je obtížná. Každá sekvence mezery, která obsahuje 1, přináší správné řazení (protože to dělá z posledního průchodu obyčejné řazení); vlastnosti takto získaných verzí Shellsortu však mohou být velmi odlišné. Příliš málo mezer zpomaluje přihrávky a příliš mnoho mezer vytváří režii.

Níže uvedená tabulka porovnává většinu dosud publikovaných navrhovaných sekvencí mezer. Některé z nich mají klesající prvky, které závisí na velikosti seřazeného pole (N). Jiné zvyšují nekonečné sekvence, jejichž prvků je méně než N by měly být použity v opačném pořadí.

OEIS	Obecný termín (k ≥ 1)	Betonové mezery	Nejhorší případ časová složitost	Autor a rok vydání
	${ displaystyle left lfloor { frac {N} {2 ^ {k}}} right rfloor}$	${ displaystyle left lfloor { frac {N} {2}} right rfloor, left lfloor { frac {N} {4}} right rfloor, ldots, 1}$	${ displaystyle Theta vlevo (N ^ {2} vpravo)}$ [např. když N = 2str]	Shell, 1959[4]
	${ displaystyle 2 left lfloor { frac {N} {2 ^ {k + 1}}} right rfloor +1}$	${ displaystyle 2 left lfloor { frac {N} {4}} right rfloor +1, ldots, 3,1}$	${ displaystyle Theta vlevo (N ^ { frac {3} {2}} vpravo)}$	Frank & Lazarus, 1960[8]
A000225	${ displaystyle 2 ^ {k} -1}$	${ displaystyle 1,3,7,15,31,63, ldots}$	${ displaystyle Theta vlevo (N ^ { frac {3} {2}} vpravo)}$	Hibbard, 1963[9]
A083318	${ displaystyle 2 ^ {k} +1}$, s předponou 1	${ displaystyle 1,3,5,9,17,33,65, ldots}$	${ displaystyle Theta vlevo (N ^ { frac {3} {2}} vpravo)}$	Papernov a Stasevich, 1965[10]
A003586	Postupná čísla formuláře ${ displaystyle 2 ^ {p} 3 ^ {q}}$ (3-hladký čísla)	${ displaystyle 1,2,3,4,6,8,9,12, ldots}$	${ displaystyle Theta left (N log ^ {2} N right)}$	Pratt, 1971[1]
A003462	${ displaystyle { frac {3 ^ {k} -1} {2}}}$, ne větší než ${ displaystyle left lceil { frac {N} {3}} right rceil}$	${ displaystyle 1,4,13,40,121, ldots}$	${ displaystyle Theta vlevo (N ^ { frac {3} {2}} vpravo)}$	Knuth, 1973,[3] na základě Pratt, 1971[1]
A036569	${ displaystyle { begin {aligned} & prod limits _ {I} a_ {q}, { hbox {where}} a_ {0} = {} & 3 a_ {q} = {} & min left {n in mathbb {N} colon n geq left ({ frac {5} {2}} right) ^ {q + 1}, forall p colon 0 leq p$	${ displaystyle 1,3,7,21,48,112, ldots}$	${ displaystyle O left (N ^ {1 + { sqrt { frac {8 ln left (5/2 right)} { ln (N)}}}} right)}$	Incerpi & Sedgewick, 1985,[11] Knuth[3]
A036562	${ displaystyle 4 ^ {k} +3 cdot 2 ^ {k-1} +1}$, s předponou 1	${ displaystyle 1,8,23,77,281, ldots}$	${ displaystyle O left (N ^ { frac {4} {3}} right)}$	Sedgewick, 1982[6]
A033622	${ displaystyle { begin {cases} 9 left (2 ^ {k} -2 ^ { frac {k} {2}} right) + 1 & k { text {even}}, 8 cdot 2 ^ {k} -6 cdot 2 ^ {(k + 1) / 2} + 1 & k { text {odd}} end {případy}}}$	${ displaystyle 1,5,19,41,109, ldots}$	${ displaystyle O left (N ^ { frac {4} {3}} right)}$	Sedgewick, 1986[12]
	${ displaystyle h_ {k} = max left { left lfloor { frac {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, ldots, 1}$	Neznámý	Gonnet & Baeza-Yates, 1991[13]
A108870	${ displaystyle left lceil { frac {1} {5}} vlevo (9 cdot left ({ frac {9} {4}} right) ^ {k-1} -4 right) right rceil}$	${ displaystyle 1,4,9,20,46,103, ldots}$	Neznámý	Tokuda, 1992[14]
A102549	Neznámé (experimentálně odvozeno)	${ displaystyle 1,4,10,23,57,132,301,701}$	Neznámý	Ciura, 2001[15]

Když binární reprezentace N obsahuje mnoho po sobě jdoucích nul, Shellsort s použitím původní sekvence mezer Shell dělá Θ (N²) srovnání v nejhorším případě. Například tento případ nastane pro N rovná se síle dvou, když prvky větší a menší než střední zaujímají liché a sudé pozice, protože jsou porovnávány pouze při posledním průchodu.

Ačkoli to má větší složitost než Ó(N logN), který je optimální pro srovnávací druhy, je vhodná pro Prattovu verzi třídění sítí a má stejnou asymptotickou složitost brány jako Batcher's bitonický třídič.

Gonnet a Baeza-Yates poznamenali, že Shellsort provádí průměrně nejméně srovnání, když jsou poměry po sobě jdoucích mezer zhruba rovné 2,2.^[13] Proto se jejich sekvence s poměrem 2,2 a Tokudova sekvence s poměrem 2,25 osvědčily. Není však známo, proč tomu tak je. Sedgewick doporučuje používat mezery, které mají nízké hodnoty největší společní dělitelé nebo jsou párové coprime.^[16]

S ohledem na průměrný počet srovnání, Ciurova posloupnost^[15] má nejznámější výkon; mezery od 701 nebyly stanoveny, ale sekvenci lze dále prodloužit podle rekurzivního vzorce ${ displaystyle h_ {k} = lfloor 2,25h_ {k-1} rfloor}$.

Tokudova sekvence, definovaná jednoduchým vzorcem ${ displaystyle h_ {k} = lceil h '_ {k} rceil}$, kde ${ displaystyle h '_ {k} = 2,25 h' _ {k-1} +1}$, ${ displaystyle h '_ {1} = 1}$, lze doporučit pro praktické aplikace.

Výpočetní složitost

Následující vlastnost platí: po h₂-třídění libovolného h₁-tříděné pole, pole zůstane h₁-tříděné.^[17] Každý h₁-tříděné a h₂-tříděné pole je také (A₁h₁+A₂h₂) -tříděné, pro všechna nezáporná celá čísla A₁ a A₂. Nejhorší případ složitosti Shellsortu je tedy spojen s Frobeniův problém: pro zadaná celá čísla h₁,..., h_n s gcd = 1, číslo Frobenius G(h₁,..., h_n) je největší celé číslo, které nelze reprezentovat jako A₁h₁+ ... +A_nh_n s nezáporným celým číslem A₁,..., A_n. Pomocí známých vzorců pro čísla Frobenius můžeme určit nejhorší složitost Shellsortu pro několik tříd posloupností mezer.^[18] Osvědčené výsledky jsou uvedeny ve výše uvedené tabulce.

Pokud jde o průměrný počet operací, žádný z prokázaných výsledků se netýká praktické sekvence mezer. Pro mezery, které jsou mocninami dvou, vypočítal Espelid tento průměr jako ${ displaystyle 0,5349N { sqrt {N}} - 0,4387N-0,097 { sqrt {N}} + O (1)}$.^[19] Knuth určila průměrnou složitost třídění N-prvkové pole se dvěma mezerami (h, 1) být ${ displaystyle { frac {2N ^ {2}} {h}} + { sqrt { pi N ^ {3} h}}}$.^[3] Z toho vyplývá, že dvouprůchodový Shellsort s h = Θ (N^1/3) dělá v průměru Ó(N^5/3) srovnání / inverze / doba chodu. Yao zjistil průměrnou složitost třípásmového Shellsortu.^[20] Jeho výsledek vylepšili Janson a Knuth:^[21] průměrný počet srovnání / inverzí / doby chodu provedených během Shellsortu se třemi mezerami (ch, srov, 1), kde h a G jsou coprime, je ${ displaystyle { frac {N ^ {2}} {4ch}} + O (N)}$ při prvním průchodu ${ displaystyle { frac {1} {8g}} { sqrt { frac { pi} {ch}}} (h-1) N ^ {3/2} + O (hN)}$ ve druhém průchodu a ${ displaystyle psi (h, g) N + { frac {1} {8}} { sqrt { frac { pi} {c}}} (c-1) N ^ {3/2} + O left ((c-1) gh ^ {1/2} N right) + O left (c ^ {2} g ^ {3} h ^ {2} right)}$ ve třetím průchodu. ψ(h, G) v posledním vzorci je složitá funkce asymptoticky rovná ${ displaystyle { sqrt { frac { pi h} {128}}} g + O left (g ^ {- 1/2} h ^ {1/2} right) + O left (gh ^ {-1/2} vpravo)}$. Zejména když h = Θ (N^7/15) a G = Θ (N^1/5), je průměrná doba třídění Ó(N^23/15).

Na základě experimentů se předpokládá, že Shellsort Hibbard běží sekvence mezer Ó(N^5/4) průměrný čas,^[3] a že sekvence Gonnet a Baeza-Yates vyžaduje průměrně 0,41NlnN(ln lnN+1/6) pohyby prvků.^[13] Aproximace průměrného počtu operací dříve předložených pro jiné sekvence selžou, když seřazená pole obsahují miliony prvků.

Níže uvedený graf ukazuje průměrný počet srovnání prvků v různých variantách Shellsortu vydělený teoretickou dolní mezí, tj. Log₂N!, kde byla podle vzorce prodloužena sekvence 1, 4, 10, 23, 57, 132, 301, 701 ${ displaystyle h_ {k} = lfloor 2,25h_ {k-1} rfloor}$.

Uplatnění teorie Kolmogorovova složitost, Jiang, Li, a Vitányi prokázal následující dolní mez pro pořadí průměrného počtu operací / doby chodu v a str-pass Shellsort: Ω (pN^1+1/str) když str≤log₂N a Ω (pN) když str> přihlásit₂N.^[22] Proto má Shellsort vyhlídky na běh v průměrném čase, který asymptoticky roste NlogN pouze při použití sekvencí mezer, jejichž počet mezer roste úměrně k logaritmu velikosti pole. Není však známo, zda Shellsort může dosáhnout tohoto asymptotického řádu průměrné složitosti, což je optimální pro srovnávací druhy. Dolní mez byla vylepšena o Vitányi^[23] pro každý počet průchodů ${ displaystyle p}$ na ${ displaystyle Omega (N součet _ {k = 1} ^ {p} h_ {k-1} / h_ {k})}$kde ${ displaystyle h_ {0} = N}$. Tento výsledek znamená například dolní hranici Jiang-Li-Vitányi pro všechny ${ displaystyle p}$-pass přírůstkové sekvence a vylepšuje dolní mez pro konkrétní přírůstkové sekvence. Ve skutečnosti jsou všechny dolní hranice (dolní a horní) aktuálně známé pro průměrný případ přesně shodovány s touto dolní mezí. Například to dává nový výsledek Janson -Knuth horní mez je porovnána s výslednou dolní mezí pro použitou přírůstkovou sekvenci, což ukazuje, že třípásmový Shellsort pro tuto přírůstkovou sekvenci používá ${ displaystyle Theta (N ^ {23/15})}$ srovnání / inverze / doba chodu. Vzorec nám umožňuje hledat přírůstkové sekvence, které dávají dolní hranice, které nejsou známy; například přírůstková sekvence pro čtyři průchody, která má dolní hranici větší než ${ displaystyle Omega (pn ^ {1 + 1 / p}) = Omega (n ^ {5/4})}$ pro přírůstkovou sekvenci${ displaystyle h_ {1} = n ^ {11/16}, h_ {2} = n ^ {7/16}, h_ {3} = n ^ {3/16}, h_ {4} = 1}$. Dolní mez se stává${ displaystyle T = Omega (n cdot (n ^ {1-11 / 16} + n ^ {11 / 16-7 / 16} + n ^ {7 / 16-3 / 16} + n ^ {3 / 16}) = Omega (n ^ {1 + 5/16}) = Omega (n ^ {21/16}).}$

Nejhorší složitost jakékoli verze Shellsortu je vyššího řádu: Plaxton, Poonen, a Suel ukázal, že roste minimálně stejně rychle jako ${ displaystyle Omega left (N left ({{ log N} over { log log N}} right) ^ {2} right)}$.^[24]

Aplikace

Shellsort provádí více operací a má vyšší poměr chybějících mezipaměti než quicksort. Protože jej však lze implementovat pomocí malého kódu a nepoužívá zásobník volání, některé implementace qsort funkce v C standardní knihovna zaměřeno na vestavěné systémy použijte místo rychlého třídění. Shellsort se například používá v uClibc knihovna.^[25] Z podobných důvodů byl v minulosti Shellsort používán v EU Linuxové jádro.^[26]

Shellsort může také sloužit jako sub-algoritmus introspektivní řazení, třídit krátké dílčí pole a zabránit zpomalení, když hloubka rekurze překročí daný limit. Tento princip se používá například v bzip2 kompresor.^[27]

Viz také

• Hřeben třídění

Reference

Bibliografie

• Knuth, Donald E. (1997). "Shellova metoda". Umění počítačového programování. Svazek 3: Třídění a vyhledávání (2. vyd.). Reading, Massachusetts: Addison-Wesley. 83–95. ISBN  978-0-201-89685-5.
• Analýza Shellsort a souvisejících algoritmů, Robert Sedgewick, Čtvrté evropské symposium o algoritmech, Barcelona, ​​září 1996.

externí odkazy

• Animované algoritmy řazení: Třídění podle prostředí na Wayback Machine (archivováno 10. března 2015) - grafická ukázka
• Shellsort s mezerami 5, 3, 1 jako maďarský lidový tanec