Schelpensort - Shellsort

Shellsort

Shellsort met gaten 23, 10, 4, 1 in actie
Klas	Sorteeralgoritme
Data structuur	Array
Prestaties in het slechtste geval	O( n 2 ) (meest bekende worst case gap sequentie) O( n log 2 n ) (best bekende worst case gap sequentie)
Prestaties in het beste geval	O( n log n ) (meeste gap-reeksen) O( n log 2 n ) (meest bekende worst-case gap-reeks)
Gemiddelde prestatie	hangt af van de volgorde van de tussenruimte
Worst-case ruimtecomplexiteit	О( n ) totaal, O(1) hulp

Paren van items verwisselen in opeenvolgende stappen van Shellsort met gaten 5, 3, 1

Shellsort , ook wel bekend als Shell sort of Shell's methode , is een in-place vergelijkende sortering . Het kan worden gezien als een veralgemening van sorteren op uitwisseling ( bubbelsortering ) of sorteren op invoeging ( invoegsortering ). De methode begint met het sorteren van paren elementen ver van elkaar, en verkleint vervolgens geleidelijk de afstand tussen de te vergelijken elementen. Door te beginnen met ver uit elkaar liggende elementen, kan het sommige elementen die niet op hun plaats zijn sneller op hun plaats worden gebracht dan een eenvoudige dichtstbijzijnde buurcentrale. Donald Shell publiceerde de eerste versie van dit soort in 1959. De looptijd van Shellsort is sterk afhankelijk van de hiaat-volgorde die het gebruikt. Voor veel praktijkvarianten blijft het bepalen van hun tijdscomplexiteit een open probleem .

Beschrijving

Shellsort is een optimalisatie van invoegsortering waarmee items die ver uit elkaar liggen kunnen worden uitgewisseld. Het idee is om de lijst met elementen zo te ordenen dat, overal beginnend, het nemen van elk h e element een gesorteerde lijst oplevert. Van zo'n lijst wordt gezegd dat hij h- gesorteerd is. Het kan ook worden gezien als h interleaved lijsten, elk afzonderlijk gesorteerd. Door met grote waarden van h te beginnen, kunnen elementen grote afstanden afleggen in de oorspronkelijke lijst, waardoor grote hoeveelheden wanorde snel worden verminderd en er minder werk overblijft voor kleinere h- sorteerstappen. Als de lijst dan k-gesorteerd wordt op een kleiner geheel getal k , dan blijft de lijst h- gesorteerd. Als u dit idee voor een afnemende reeks h- waarden die op 1 eindigt, volgt, blijft er gegarandeerd een gesorteerde lijst achter.

In simplistische termen betekent dit dat als we een array van 1024 getallen hebben, onze eerste opening ( h ) 512 zou kunnen zijn. We doorlopen dan de lijst en vergelijken elk element in de eerste helft met het element in de tweede helft. Onze tweede opening ( k ) is 256, wat de array in vier secties verdeelt (beginnend bij 0,256,512,768), en we zorgen ervoor dat de eerste items in elke sectie relatief ten opzichte van elkaar worden gesorteerd, dan het tweede item in elke sectie, enzovoort . In de praktijk kan de tussenruimte van alles zijn, maar de laatste tussenruimte is altijd 1 om de sortering te beëindigen (effectief eindigen met een gewone invoegsortering).

Een voorbeeld van Shellsort met gaten 5, 3 en 1 wordt hieronder getoond.

De eerste doorgang, 5-sortering, voert invoegsortering uit op vijf afzonderlijke subarrays ( a ₁ , a ₆ , a ₁₁ ), ( a ₂ , a ₇ , a ₁₂ ), ( a ₃ , a ₈ ), ( a ₄ , a ₉ ), ( een ₅ , een ₁₀ ). Het verandert bijvoorbeeld de subarray ( a ₁ , a ₆ , a ₁₁ ) van (62, 17, 25) in (17, 25, 62). De volgende pas, 3-sortering, voert invoegsortering uit op de drie subarrays ( a ₁ , a ₄ , a ₇ , a ₁₀ ), ( a ₂ , a ₅ , a ₈ , a ₁₁ ), ( a ₃ , a ₆ , een ₉ , een ₁₂ ). De laatste pas, 1-sortering, is een gewone invoegsoort van de hele array ( a ₁ ,..., a ₁₂ ).

Zoals het voorbeeld illustreert, zijn de subarrays waarop Shellsort werkt aanvankelijk kort; later zijn ze langer maar bijna besteld. In beide gevallen werkt invoegsortering efficiënt.

Shellsort is niet stabiel : het kan de relatieve volgorde van elementen met gelijke waarden veranderen. Het is een adaptief sorteeralgoritme omdat het sneller wordt uitgevoerd wanneer de invoer gedeeltelijk is gesorteerd.

Pseudocode

Met behulp van Marcin Ciura's gap-reeks, met een innerlijke insertie-sortering.

# 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
    }
}

Gap-reeksen

De vraag om te beslissen welke gap-sequentie moet worden gebruikt, is moeilijk. Elke gap-reeks die 1 bevat, levert een juiste sortering op (omdat dit de laatste pas een gewone invoegsortering maakt); de eigenschappen van de aldus verkregen versies van Shellsort kunnen echter heel verschillend zijn. Te weinig tussenruimten vertraagt ​​de passen, en te veel tussenruimten zorgen voor overhead.

De onderstaande tabel vergelijkt de meeste voorgestelde gap-sequenties die tot nu toe zijn gepubliceerd. Sommigen van hen hebben afnemende elementen die afhankelijk zijn van de grootte van de gesorteerde array ( N ). Anderen zijn toenemende oneindige reeksen, waarvan de elementen kleiner dan N in omgekeerde volgorde moeten worden gebruikt.

OEIS	Algemene term ( k 1)	Betonnen gaten	Worst-case tijd complexiteit	Auteur en jaar van uitgave
	${\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)}$[bijv. wanneer 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)}$	Hibard , 1963
A083318	${\displaystyle 2^{k}+1}$, voorafgegaan door 1	${\displaystyle 1,3,5,9,17,33,65,\ldots}$	${\displaystyle \Theta \left(N^{\frac {3}{2}}\right)}$	Papernov & Stasevich, 1965
A003586	Opeenvolgende nummers van het formulier ( 3-gladde nummers) ${\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}}}$, niet groter dan ${\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, gebaseerd op Pratt , 1971
A036569	${\displaystyle {\begin{uitgelijnd}&\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{uitgelijnd}}}$	${\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}$, voorafgegaan door 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\rverdieping -1\right\rverdieping ,\ldots ,1}$	Onbekend	Gonnet & Baeza-Yates , 1991
A108870	${\displaystyle \left\lceil {\frac {1}{5}}\left(9\cdot \left({\frac {9}{4}}\right)^{k-1}-4\right) \rechts\rceil }$	${\displaystyle 1,4,9,20,46,103,\ldots}$	Onbekend	Tokuda, 1992
A102549	Onbekend (experimenteel afgeleid)	${\displaystyle 1,4,10,23,57,132,301.701}$	Onbekend	Ciura, 2001

Wanneer de binaire representatie van N veel opeenvolgende nullen bevat, maakt Shellsort in het slechtste geval met behulp van de oorspronkelijke gap-reeks van Shell Θ( N ² ) -vergelijkingen . Dit geval doet zich bijvoorbeeld voor voor N gelijk aan een macht van twee wanneer elementen groter en kleiner dan de mediaan respectievelijk oneven en even posities innemen, omdat ze alleen in de laatste doorgang worden vergeleken.

Hoewel het een hogere complexiteit heeft dan de O ( N  log  N ) die optimaal is voor vergelijkende sorteringen, leent de versie van Pratt zich voor het sorteren van netwerken en heeft het dezelfde asymptotische poortcomplexiteit als de bitonische sorteerder van Batcher .

Gonnet en Baeza-Yates merkten op dat Shellsort gemiddeld de minste vergelijkingen maakt wanneer de verhoudingen van opeenvolgende hiaten ongeveer gelijk zijn aan 2,2. Dit is de reden waarom hun reeks met verhouding 2.2 en Tokuda's reeks met verhouding 2.25 efficiënt blijken te zijn. Het is echter niet bekend waarom dit zo is. Sedgewick raadt aan om hiaten te gebruiken met een lage grootste gemene deler of die paarsgewijs coprime zijn .

Met betrekking tot het gemiddelde aantal vergelijkingen heeft de sequentie van Ciura de meest bekende prestatie; hiaten vanaf 701 werden niet bepaald, maar de reeks kan verder worden uitgebreid volgens de recursieve formule . ${\displaystyle h_{k}=\lfloor 2.25h_{k-1}\rfloor }$

Tokuda's sequentie, gedefinieerd door de eenvoudige formule , waar , , kan worden aanbevolen voor praktische toepassingen. ${\displaystyle h_{k}=\lceil h'_{k}\rceil}$${\displaystyle h'_{k}=2.25h'_{k-1}+1}$${\displaystyle h'_{1}=1}$

Als de maximale invoergrootte klein is, zoals kan gebeuren als Shellsort wordt gebruikt op kleine subarrays door een ander recursief sorteeralgoritme zoals quicksort of merge sort , dan is het mogelijk om een ​​optimale volgorde voor elke invoergrootte in tabelvorm te brengen.

Computationele complexiteit

De volgende eigenschap geldt: na h ₂ -sortering van een willekeurige h ₁ -sorted array, blijft de array h ₁ -sorted. Elke h ₁ -gesorteerde en h ₂ -gesorteerde array is ook ( a ₁ h ₁ + a ₂ h ₂ ) -gesorteerd, voor alle niet-negatieve gehele getallen een ₁ en een ₂ . De worst-case complexiteit van Shellsort hangt dus samen met het Frobenius-probleem : voor gegeven gehele getallen h ₁ ,..., h _n met ggd = 1, is het Frobenius-getal g ( h ₁ ,..., h _n ) het grootst geheel getal dat niet kan worden weergegeven als een ₁ h ₁ + ... + een _n h _n met een niet-negatief geheel getal a ₁ ,..., een _n . Met behulp van bekende formules voor Frobenius-getallen kunnen we de worst-case complexiteit van Shellsort bepalen voor verschillende klassen van gap-reeksen. Bewezen resultaten zijn weergegeven in de bovenstaande tabel.

Met betrekking tot het gemiddeld aantal operaties betreft geen van de bewezen resultaten een praktische gap-sequentie. Voor hiaten die machten van twee zijn, berekende Espelid dit gemiddelde als . Knuth bepaalde de gemiddelde complexiteit van het sorteren van een N- element-array met twee gaten ( h , 1) te zijn . Hieruit volgt dat een Shellsort met twee doorgangen met h = Θ( N ^1/3 ) gemiddeld O ( N ^5/3 ) vergelijkingen/inversies/looptijd maakt. Yao vond de gemiddelde complexiteit van een Shellsort met drie doorgangen. Zijn resultaat werd verfijnd door Janson en Knuth: het gemiddelde aantal vergelijkingen/inversies/looptijd gemaakt tijdens een Shellsort met drie gaten ( ch , cg , 1), waarbij h en g coprime zijn, is in de eerste doorgang, in de tweede pas en in de derde pas. ψ ( h , g ) in de laatste formule is een gecompliceerde functie die asymptotisch gelijk is aan . In het bijzonder, wanneer h = Θ( N ^7/15 ) en g = Θ( N ^1/5 ), is de gemiddelde sorteertijd 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}\rechts)}$

Op basis van experimenten wordt vermoed dat Shellsort met Hibbard 's gap-reeks in de gemiddelde tijd O ( N ^5/4 ) loopt , en dat de reeks van Gonnet en Baeza-Yates gemiddeld 0,41 N  ln  N vereist  (ln ln  N  + 1/6 ) element beweegt. Benaderingen van het gemiddelde aantal bewerkingen dat voorheen voor andere reeksen werd voorgesteld, mislukken wanneer gesorteerde arrays miljoenen elementen bevatten.

Onderstaande grafiek toont het gemiddelde aantal elementvergelijkingen in verschillende varianten van Shellsort, gedeeld door de theoretische ondergrens, namelijk log ₂ N !, waarbij de rij 1, 4, 10, 23, 57, 132, 301, 701 is verlengd volgens de formule . ${\displaystyle h_{k}=\lfloor 2.25h_{k-1}\rfloor }$

Door de theorie van Kolmogorov-complexiteit toe te passen , bewezen Jiang, Li en Vitányi de volgende ondergrens voor de volgorde van het gemiddelde aantal bewerkingen/looptijd in een p- pass Shellsort: Ω( pN ^{1+1/ p} ) wanneer p  ≤ log ₂ N en Ω( pN ) wanneer p  > log ₂ N . Daarom heeft Shellsort vooruitzichten om te werken in een gemiddelde tijd die asymptotisch groeit als N log N, alleen bij het gebruik van gap-reeksen waarvan het aantal hiaten groeit in verhouding tot de logaritme van de arraygrootte. Het is echter niet bekend of Shellsort deze asymptotische orde van gemiddelde complexiteit kan bereiken, wat optimaal is voor vergelijkingssoorten. De ondergrens werd verbeterd door Vitányi voor elk aantal passen naar waar . Dit resultaat houdt bijvoorbeeld de ondergrens van Jiang-Li-Vitányi in voor all- pass increment-reeksen en verbetert die ondergrens voor bepaalde increment-reeksen. In feite worden alle grenzen (onder- en bovengrens) die momenteel bekend zijn voor het gemiddelde geval precies geëvenaard door deze ondergrens. Dit geeft bijvoorbeeld het nieuwe resultaat dat de bovengrens van Janson-Knuth overeenkomt met de resulterende ondergrens voor de gebruikte incrementreeks, wat aantoont dat Shellsort bij drie passages voor deze incrementreeks vergelijkingen/inversies/looptijd gebruikt. Met de formule kunnen we zoeken naar incrementele reeksen die onbekende ondergrenzen opleveren; bijvoorbeeld een incrementele reeks voor vier passages die een ondergrens heeft die groter is dan voor de incrementele reeks . De ondergrens wordt ${\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}).}$

De worst-case complexiteit van elke versie van shellsort is van hogere orde: Plaxton, Poonen en Suel toonde aan dat het groeit in ieder geval zo snel . ${\ Displaystyle \ Omega \ left (N \ left ({\ log N \ over \ log \ log N} \ right) ^ {2} \ right)}$

Toepassingen

Shellsort voert meer bewerkingen uit en heeft een hogere cache-miss-ratio dan quicksort . Omdat het echter met weinig code kan worden geïmplementeerd en de call-stack niet gebruikt , gebruiken sommige implementaties van de qsort- functie in de C-standaardbibliotheek die gericht is op embedded systemen het in plaats van quicksort. Shellsort wordt bijvoorbeeld gebruikt in de uClibc- bibliotheek. Om soortgelijke redenen werd Shellsort in het verleden gebruikt in de Linux-kernel .

Shellsort kan ook dienen als een subalgoritme van introspectieve sortering , om korte subarrays te sorteren en om vertraging te voorkomen wanneer de recursiediepte een bepaalde limiet overschrijdt. Dit principe wordt bijvoorbeeld toegepast in de bzip2- compressor.

Zie ook

• Kam sorteren

Referenties

Bibliografie

• Knuth, Donald E. (1997). "Shell's methode". De kunst van computerprogrammeren. Deel 3: Sorteren en zoeken (2e ed.). Reading, Massachusetts: Addison-Wesley. blz. 83-95. ISBN 978-0-201-89685-5.
• Analyse van Shellsort en gerelateerde algoritmen , Robert Sedgewick, vierde Europees symposium over algoritmen, Barcelona, ​​september 1996.

Externe links

• Geanimeerde sorteeralgoritmen: Shell Sort at the Wayback Machine (gearchiveerd 10 maart 2015) - grafische demonstratie
• Shellsort met gaten 5, 3, 1 als Hongaarse volksdans