Shellsort - Shellsort

Shellsort

Shellsort s mezerami 23, 10, 4, 1 v akci
Třída	Algoritmus řazení
Datová struktura	Pole
Nejhorší výkon	O ( n 2 ) (nejhorší známá nejhorší mezerová sekvence) O ( n log 2 n ) (nejznámější nejhorší případová mezerová sekvence)
Nejlepší výkon	O ( n log n ) (většina sekvencí mezer) O ( n log 2 n ) (nejznámější sekvence mezer v nejhorším případě)
Průměrný výkon	závisí na mezerové sekvenci
Nejhorší prostorová složitost	О ( n ) celkem, O (1) pomocný

Prohození dvojic položek v postupných krocích Shellsortu s mezerami 5, 3, 1

Shellsort , také známý jako Shell sort nebo Shellova metoda , je srovnání na místě . Může být vnímáno buď jako zobecnění řazení podle výměny ( bublinkové řazení ), nebo řazení podle vložení ( vkládací řazení ). Metoda začíná tříděním párů prvků daleko od sebe, poté postupným zmenšováním mezery mezi porovnávanými prvky. Začínáme-li s prvky daleko od sebe, může přesunout některé nemístné prvky do polohy rychleji než jednoduchá výměna nejbližších sousedů. Donald Shell publikoval první verzi tohoto druhu v roce 1959. Doba běhu Shellsortu je silně závislá na sekvenci mezer, kterou používá. U mnoha praktických variant zůstává určení jejich časové náročnosti otevřeným problémem .

Popis

Shellsort je optimalizace typu vkládání, která umožňuje výměnu položek, které jsou daleko od sebe. Cílem je uspořádat seznam prvků tak, aby počínaje kdekoli, každý h th prvek vytvořil seřazený seznam. Takový seznam je prý h -tříděný. Lze jej také považovat za h proložené seznamy, každý jednotlivě seřazený. Počínaje velkými hodnotami h umožňuje prvkům pohybovat se v původním seznamu na dlouhé vzdálenosti, což rychle snižuje velké množství nepořádku a ponechává méně práce pro menší h -sort kroky. Pokud je seznam potom k -seřazen pro nějaké menší celé číslo k , pak seznam zůstane h -sorted. Podle této myšlenky na klesající posloupnost hodnot h končících na 1 je zaručeno, že na konci zůstane seřazený seznam.

Zjednodušeně to znamená, že pokud máme pole 1024 čísel, naše první mezera ( h ) by mohla být 512. Poté procházíme seznamem a porovnáváme 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 pro dokončení třídění (efektivní dokončení obyčejným vložením).

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

První průchod, třídění, provádí třídění vkládání na pět samostatných podoblastí ( a ₁ , a ₆ , a ₁₁ ), ( a ₂ , a ₇ , a ₁₂ ), ( a ₃ , a ₈ ), ( a ₄ , a ₉ ), ( a ₅ , a ₁₀ ). Například změní podoblast ( a ₁ , a ₆ , a ₁₁ ) z (62, 17, 25) na (17, 25, 62). Další průchod, třídění, provede třídění vložení na tři dílčí pole ( a ₁ , a ₄ , a ₇ , a ₁₀ ), ( a ₂ , a ₅ , a ₈ , a ₁₁ ), ( a ₃ , a ₆ , a ₉ , a ₁₂ ). Poslední průchod, 1-třídění, je obyčejný vkládací druh celého pole ( a ₁ , ..., a ₁₂ ).

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

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

Pseudo kód

Použití mezerové sekvence Marcina Ciury s vnitřním zařazením.

# Sort an array a[0...n-1].
gaps = [701, 301, 132, 57, 23, 10, 4, 1]  // Ciura gap sequence

# Start with the largest gap and work down to a gap of 1
foreach (gap in gaps)
{
    # Do a gapped insertion sort for this gap size.
    # The first gap elements a[0..gap-1] are already in gapped order
    # keep adding one more element until the entire array is gap sorted
    for (i = gap; i < n; i += 1)
    {
        # add a[i] to the elements that have been gap sorted
        # save a[i] in temp and make a hole at position i
        temp = a[i]
        # shift earlier gap-sorted elements up until the correct location for a[i] is found
        for (j = i; j >= gap and a[j - gap] > temp; j -= gap)
        {
            a[j] = a[j - gap]
        }
        # put temp (the original a[i]) in its correct location
        a[j] = temp
    }
}

Sekvence mezer

Otázka rozhodnout, kterou sekvenci mezer použít, je obtížná. Každá mezerová sekvence, která obsahuje 1, poskytuje správné řazení (protože to činí konečný průchod obyčejným vkládacím tříděním); vlastnosti takto získaných verzí Shellsortu se však mohou velmi lišit. 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 navržených sekvencí mezer. Některé z nich mají klesající prvky, které závisí na velikosti tříděného pole ( N ). Jiné zvyšují nekonečné sekvence, jejichž prvky menší než N by měly být použity v opačném pořadí.

OEIS	Obecný termín ( k ≥ 1)	Betonové mezery	Časová složitost v nejhorším případě	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 \ left (N^{2} \ right)}$[např. když N = 2 p ]	Shell , 1959
	${\ 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 \ left (N^{\ frac {3} {2}} \ right)}$	Frank & Lazarus, 1960
A000225	${\ Displaystyle 2^{k} -1}$	${\ Displaystyle 1,3,7,15,31,63, \ ldots}$	${\ displaystyle \ Theta \ left (N^{\ frac {3} {2}} \ right)}$	Hibbard , 1963
A083318	${\ displaystyle 2^{k} +1}$s předponou 1	${\ Displaystyle 1,3,5,9,17,33,65, \ ldots}$	${\ displaystyle \ Theta \ left (N^{\ frac {3} {2}} \ right)}$	Papernov a Staševič, 1965
A003586	Po sobě jdoucí čísla formuláře ( 3 hladká čísla) ${\ Displaystyle 2^{p} 3^{q}}$	${\ Displaystyle 1,2,3,4,6,8,9,12, \ ldots}$	${\ displaystyle \ Theta \ left (N \ log ^{2} N \ right)}$	Pratt , 1971
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 \ left (N^{\ frac {3} {2}} \ right)}$	Knuth , 1973, podle Pratt , 1971
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 <q \ Rightarrow \ gcd (a_ {p}, n) = 1 \ right \} \\ I = {} & \ left \ {0 \ leq q <r \ mid q \ neq {\ frac {1} { 2}} \ left (r^{2}+r \ right) -k \ right \} \\ r = {} & \ left \ lfloor {\ sqrt {2k+{\ sqrt {2k}}}} \ right \ rfloor \ end {aligned}}}$	${\ 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, Knuth
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
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 {cases}}}$	${\ Displaystyle 1,5,19,41,109, \ ldots}$	${\ Displaystyle O \ left (N^{\ frac {4} {3}} \ right)}$	Sedgewick, 1986
	${\ Displaystyle h_ {k} = \ max \ left \ {\ left \ lfloor {\ frac {5h_ {k-1} -1} {11}} \ right \ rfloor, 1 \ right \}, h_ {0} = N}$	${\ Displaystyle \ left \ lfloor {\ frac {5N-1} {11}} \ right \ rfloor, \ left \ lfloor {\ frac {5} {11}} \ left \ lfloor {\ frac {5N-1} {11}} \ right \ rfloor -1 \ right \ rfloor, \ ldots, 1}$	Neznámý	Gonnet & Baeza-Yates , 1991
A108870	${\ Displaystyle \ left \ lceil {\ frac {1} {5}} \ left (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
A102549	Neznámý (experimentálně odvozený)	${\ Displaystyle 1,4,10,23,57,132,301,701}$	Neznámý	Ciura, 2001

Když binární reprezentace N obsahuje mnoho po sobě jdoucích nul, Shellsort pomocí Shellovy původní mezerové sekvence provede srovnání Θ ( N ² ) v nejhorším případě. Například tento případ nastává pro N rovný síle dvou, když prvky větší a menší než medián zaujímají liché a sudé pozice, protože jsou porovnávány pouze v posledním průchodu.

Přestože má Prattova verze vyšší složitost než O ( N  log  N ), která je optimální pro srovnávací druhy, je vhodná k třídění sítí a má stejnou asymptotickou složitost brány jako Batcherův bitonický třídič .

Gonnet a Baeza-Yates zjistili, že Shellsort provádí v průměru nejméně srovnání, když jsou poměry po sobě jdoucích mezer zhruba stejné jako 2,2. Proto se jejich sekvence s poměrem 2,2 a Tokudova sekvence s poměrem 2,25 ukázala jako účinná. Není však známo, proč tomu tak je. Sedgewick doporučuje použít mezery, které mají nízké největší společné dělitele nebo jsou párové coprime .

S ohledem na průměrný počet srovnání má sekvence Ciury nejznámější výkon; mezery ze 701 nebyly stanoveny, ale sekvenci lze dále prodloužit podle rekurzivního vzorce . ${\ Displaystyle h_ {k} = \ lfloor 2.25h_ {k-1} \ rfloor}$

Tokuda je sekvence, které jsou definovány pomocí jednoduchého vzorce , kde , , lze doporučit pro praktické aplikace. ${\ Displaystyle h_ {k} = \ lceil h '_ {k} \ rceil}$${\ Displaystyle h '_ {k} = 2,25 h' _ {k-1} +1}$${\ displaystyle h '_ {1} = 1}$

Pokud je maximální velikost vstupu malá, což může nastat, pokud je Shellsort používán na malých dílčích polích jiným algoritmem rekurzivního řazení, jako je rychlé řazení nebo sloučení , pak je možné pro každou velikost vstupu vytvořit tabulku s optimální sekvencí.

Výpočetní náročnost

Platí následující vlastnost: po h ₂ -třídění jakéhokoli h ₁ -tříděného pole, pole zůstane h ₁ -tříděno. Každý h ₁ -sorted a h ₂ -sorted pole je také ( ₁ h ₁ + ₂ H ₂ ) -sorted, pro jakékoliv nezáporné celá čísla ₁ a ₂ . Složitost Shellsortu v nejhorším případě je tedy spojena s Frobeniusovým problémem : pro daná celá čísla h ₁ , ..., h _n s gcd = 1 je Frobeniusovo číslo g ( h ₁ , ..., h _n ) největší celé číslo, které nemohou být reprezentován jako v ₁ h ₁ + ... + _n h _n s nezáporné celé číslo z ₁ , ..., a _n . Pomocí známých vzorců pro čísla Frobenius můžeme určit nejhorší složitost Shellsortu pro několik tříd mezerových sekvencí. 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é mezery. Pro mezery, které jsou mocninami dvou, vypočítal Espelid tento průměr jako . Knuth určil průměrnou složitost třídění pole N -prvku se dvěma mezerami ( h , 1) na . Z toho vyplývá, že dvouprůchodový Shellsort s h = Θ ( N ^1/3 ) činí v průměru O ( N ^5/3 ) srovnání/inverze/doba běhu. Yao zjistil průměrnou složitost tříprůchodového Shellsortu. Jeho výsledek zpřesnili Janson a Knuth: průměrný počet srovnání/inverzí/doby běhu provedeného během Shellsortu se třemi mezerami ( ch , cg , 1), kde h a g jsou coprime, je v prvním průchodu, ve druhém přihrávka a ve třetím průchodu. ψ ( h , g ) v posledním vzorci je komplikovaná funkce asymptoticky rovná . Zejména když h = Θ ( N ^7/15 ) a g = Θ ( N ^1/5 ), průměrná doba třídění je O ( N ^23/15 ). ${\ Displaystyle 0,5349N {\ sqrt {N}}-0,4387N-0,097 {\ sqrt {N}}+O (1)}$${\ displaystyle {\ frac {2N^{2}} {h}}+{\ sqrt {\ pi N^{3} h}}}$${\ displaystyle {\ frac {N^{2}} {4ch}}+O (N)}$${\ Displaystyle {\ frac {1} {8g}} {\ sqrt {\ frac {\ pi} {ch}}} (h-1) N^{3/2}+O (hN)}$${\ 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)}$${\ Displaystyle {\ sqrt {\ frac {\ pi h} {128}}} g+O \ left (g^{-1/2} h^{1/2} \ right)+O \ left (gh^ {-1/2} \ right)}$

Na základě experimentů, to je se domníval, že ShellSort s Hibbard je mezera sekvence běží v O ( N ^5/4 ) průměrná doba, a že Gonnet a Baeza-Yates Sekvence vyžaduje v průměru o 0,41 N  ln  N  (ln ln  N  + 1/6 ) prvek se pohybuje. Přibližování průměrného počtu operací dříve předložených pro jiné sekvence selže, když seřazená pole obsahují miliony prvků.

Níže uvedený graf ukazuje průměrný počet porovnání prvků v různých variantách Shellsortu dělený teoretickou dolní mezí, tj. Log ₂ N !, Kde byla rozšířena sekvence 1, 4, 10, 23, 57, 132, 301, 701 podle vzorce . ${\ Displaystyle h_ {k} = \ lfloor 2.25h_ {k-1} \ rfloor}$

Použitím teorie Kolmogorovovy složitosti prokázali Jiang, Li a Vitányi následující dolní mez pro pořadí průměrného počtu operací/ doby běhu v p -pass Shellsort: Ω ( pN ^{1+1/ p} ), když p  ≤ log ₂ N a Ω ( pN ), když p  > log ₂ N . Shellsort má proto vyhlídky na běh v průměrném čase, který asymptoticky roste jako N log N 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 dokáže dosáhnout tohoto asymptotického řádu složitosti průměrných případů, které je optimální pro srovnávací druhy. Dolní hranice se zlepšila Vitányi pro každé počtu průchodů do kde . Tento výsledek implikuje například dolní hranici Jiang-Li-Vitányiho pro all-pass přírůstkové sekvence a zlepšuje tuto spodní hranici pro konkrétní přírůstkové sekvence. Ve skutečnosti jsou všechny meze (dolní a horní), které jsou v současné době známé pro průměrný případ, přesně shodné s touto dolní hranicí. Například to dává nový výsledek, že horní hranice Janson-Knuth je shodná s výslednou dolní mezí pro použitou přírůstkovou sekvenci, což ukazuje, že tříprůchodový Shellsort pro tuto přírůstkovou sekvenci používá srovnání/inverze/doba běhu. 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á spodní hranici větší než pro přírůstkovou sekvenci . Dolní mez se stává ${\ displaystyle p}$${\ Displaystyle \ Omega (N \ sum _ {k = 1}^{p} h_ {k-1}/h_ {k})}$${\ displaystyle h_ {0} = N}$${\ displaystyle p}$${\ displaystyle \ Theta (N^{23/15})}$${\ Displaystyle \ Omega (pn^{1+1/p}) = \ Omega (n^{5/4})}$${\ displaystyle h_ {1} = n^{11/16},}$ ${\ displaystyle h_ {2} = n^{7/16},}$ ${\ displaystyle h_ {3} = n^{3/16},}$ ${\ displaystyle h_ {4} = 1}$${\ 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}).}$

Složitost nejhoršího případu jakékoli verze Shellsortu je vyššího řádu: Plaxton, Poonen a Suel ukázali, že roste minimálně stejně rychle jako . ${\ Displaystyle \ Omega \ left (N \ left ({\ log N \ over \ log \ log N} \ right)^{2} \ right)}$

Aplikace

Shellsort provádí více operací a má vyšší poměr chyb mezipaměti než quicksort . Jelikož jej však lze implementovat pomocí malého kódu a nepoužívá zásobník volání , některé implementace funkce qsort ve standardní knihovně C cílené na vestavěné systémy ji používají místo quicksortu. Shellsort se například používá v knihovně uClibc . Z podobných důvodů byl v minulosti v jádře Linuxu používán Shellsort .

Shellsort může také sloužit jako subalgoritmus introspektivního třídění , k třídění krátkých dílčích polí a k prevenci zpomalení, když hloubka rekurze překročí danou mez. Tento princip se používá například v kompresoru bzip2 .

Viz také

• Hřebenové řazení

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. s. 83–95. ISBN 978-0-201-89685-5.
• Analýza Shellsortu a souvisejících algoritmů , Robert Sedgewick, Čtvrté evropské sympozium o algoritmech, Barcelona, ​​září 1996.

externí odkazy

• Algoritmy animovaného řazení: Shell Sort na Wayback Machine (archivováno 10. března 2015) - grafická ukázka
• Shellsort s mezerami 5, 3, 1 jako maďarský lidový tanec