Shellsort - Shellsort

Shellsort

Kuori, jossa on aukkoja 23, 10, 4, 1 toiminnassa
Luokka	Lajittelualgoritmi
Tietorakenne	Array
Huonoin suoritus	O ( n 2 ) (pahin tunnettu pahimman tapauksen aukkosekvenssi) O ( n log 2 n ) (tunnetuin pahin tapausjakso)
Paras esitys	O ( n log n ) (useimmat aukkosekvenssit) O ( n log 2 n ) (tunnetuin pahimmassa tapauksessa oleva aukkosekvenssi)
Keskimääräinen suorituskyky	riippuu välijärjestyksestä
Pahimmassa tapauksessa tilan monimutkaisuus	О ( n ) yhteensä, O (1) apulaite

Kohdeparien vaihtaminen Shellsortin peräkkäisissä vaiheissa aukkojen 5, 3, 1 kanssa

Shellsort , joka tunnetaan myös nimellä Shell-lajittelu tai Shell-menetelmä , on paikan päällä oleva vertailulaji . Sitä voidaan pitää joko yleistyksenä lajittelun vaihdon ( kuplalajittelu ) tai lajittelun lisäämisen ( lisäyslajittelu ) perusteella. Menetelmä alkaa lajittelemalla elementtiparit kaukana toisistaan ​​ja pienentämällä asteittain vertailtavien elementtien välistä kuilua. Aloittamalla kaukana toisistaan ​​olevista elementeistä, se voi siirtää jotkut paikoillaan olevat elementit paikalleen nopeammin kuin yksinkertainen lähimmän naapurin vaihto. Donald Shell julkaisi ensimmäisen tällaisen version vuonna 1959. Shellsortin käyttöaika riippuu suuresti käyttämästään aukkojärjestyksestä. Monien käytännön varianttien osalta niiden monimutkaisuuden määrittäminen on edelleen avoin ongelma .

Kuvaus

Shellsort on optimointi lisäyslajittelun joka mahdollistaa vaihdon kohteita, jotka ovat kaukana toisistaan. Ajatuksena on järjestää elementtiluettelo niin, että mistä tahansa alkaen jokaisen h : n elementin ottaminen tuottaa lajitellun luettelon. Tällaisen luettelon sanotaan olevan h -lajiteltu. Sitä voidaan myös ajatella h lomitetuina luetteloina, joista jokainen on lajiteltu erikseen. Suurista h -arvoista alkaen elementit voivat liikkua pitkiä matkoja alkuperäisessä luettelossa, mikä vähentää suuria häiriöitä nopeasti ja jättää vähemmän työtä pienemmille h -lajitteluvaiheille. Jos luettelo on sitten k -lajiteltu jollekin pienemmälle kokonaisluvulle k , luettelo pysyy h -lajiteltuna. Tämän ajatuksen noudattaminen h -arvojen pienenevässä sarjassa, joka päättyy 1: een, jättää varmasti lajiteltu luettelo loppuun.

Yksinkertaistettuna tämä tarkoittaa, että jos meillä on 1024 -numeroinen taulukko, ensimmäinen aukko ( h ) voisi olla 512. Käymme sitten luettelon läpi vertaamalla jokaisen ensimmäisen puoliskon elementtiä toisen puoliskon elementtiin. Toinen aukko ( k ) on 256, joka jakaa taulukon neljään osaan (alkaen 0,256,512,768), ja varmistamme, että kunkin osion ensimmäiset kohteet on lajiteltu suhteessa toisiinsa, sitten toinen kohde kussakin osassa ja niin edelleen . Käytännössä aukkosekvenssi voi olla mikä tahansa, mutta viimeinen väli on aina 1 lajittelun viimeistelemiseksi (viimeistely käytännössä tavallisella lisäyslajittelulla).

Alla on esimerkki Shellsortista, jossa on aukot 5, 3 ja 1.

Ensimmäinen siirto, 5-lajittelu, suorittaa lisäyslajittelun viidellä erillisellä alitasolla ( a ₁ , a ₆ , a ₁₁ ), ( a ₂ , a ₇ , a ₁₂ ), ( a ₃ , a ₈ ), ( a ₄ , a ₉ ), ( ₅ , ₁₀ ). Se esimerkiksi muuttaa aliryhmän ( a ₁ , a ₆ , a ₁₁ ) arvosta (62, 17, 25) arvoon (17, 25, 62). Seuraavan pass, 3-lajittelu, suorittaa se pistetään lajitella kolme alijärjestelyt ( ₁ , ₄ , ₇ , ₁₀ ), ( ₂ , ₅ , ₈ , ₁₁ ), ( ₃ , ₆ , ₉ , ₁₂ ). Viimeinen siirto, 1-lajittelu, on tavallinen lisäyslaji koko ryhmästä ( a ₁ , ..., a ₁₂ ).

Kuten esimerkki havainnollistaa, Shellsortin käyttämät alirivit ovat aluksi lyhyitä; myöhemmin ne ovat pidempiä, mutta melkein tilattuja. Molemmissa tapauksissa lisäyslajittelu toimii tehokkaasti.

Shellsort ei ole vakaa : se voi muuttaa elementtien suhteellista järjestystä yhtä suurilla arvoilla. Se on mukautuva lajittelualgoritmi , koska se suorittaa nopeammin, kun tulo on osittain lajiteltu.

Pseudokoodi

Käyttämällä Marcin Ciuran aukkosekvenssiä sisäisellä lisäyslajikkeella.

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

Kysymys siitä, mitä aukkoa käytetään, on vaikea päättää. Jokainen aukkosarja, joka sisältää yhden, antaa oikean lajittelun (koska tämä tekee viimeisestä passista tavallisen lisäyslajittelun); näin saatujen Shellsort -versioiden ominaisuudet voivat kuitenkin olla hyvin erilaisia. Liian vähän aukkoja hidastaa syöttöjä ja liian monet aukot aiheuttavat yleiskustannuksia.

Alla olevassa taulukossa verrataan useimpia tähän mennessä julkaistuja ehdotettuja aukkosekvenssejä. Joissakin niistä on pieneneviä elementtejä, jotka riippuvat lajiteltujen matriisien ( N ) koosta . Toiset lisäävät äärettömiä sekvenssejä, joiden elementtejä, jotka ovat pienempiä kuin N, tulisi käyttää päinvastaisessa järjestyksessä.

OEIS	Yleinen termi ( k ≥ 1)	Betoniset aukot	Pahimman ajan monimutkaisuus	Tekijä ja julkaisuvuosi
	${\ 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)}$[esim. kun 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}$, etuliite 1	${\ displaystyle 1,3,5,9,17,33,65, \ ldots}$	${\ displaystyle \ Theta \ left (N^{\ frac {3} {2}} \ right)}$	Papernov & Stasevich, 1965
A003586	Lomakkeen peräkkäiset numerot ( 3 tasaista numeroa) ${\ 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}}}$, ei suurempi kuin ${\ 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, perustuu Pratt , 1971
A036569	${\ displaystyle {\ begin {aligned} & \ prod \ limits _ {I} a_ {q}, {\ hbox {where}} \\ a_ {0} = {} & 3 \\ a_ {q} = {} & \ min \ vasen \ {n \ in \ mathbb {N} \ kaksoispiste n \ geq \ vasen ({\ frac {5} {2}} \ oikea)^{q+1}, \ kaikki p \ kaksoispiste 0 \ leq p <q \ Oikea nuoli \ gcd (a_ {p}, n) = 1 \ oikea \} \\ I = {} & \ vasen \ {0 \ leq q <r \ mid q \ neq {\ frac {1} { 2}} \ vasen (r^{2}+r \ oikea) -k \ oikea \} \\ r = {} & \ vasen \ l-kerros {\ sqrt {2k+{\ sqrt {2k}}}} \ oikea \ rfloor \ end {aligned}}}$	${\ displaystyle 1,3,7,21,48,112, \ ldots}$	${\ displaystyle O \ vasen (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}$, etuliite 1	${\ displaystyle 1,8,23,77,281, \ ldots}$	${\ displaystyle O \ vasen (N^{\ frac {4} {3}} \ oikea)}$	Sedgewick, 1982
A033622	${\ displaystyle {\ begin {case} 9 \ vasen (2^{k} -2^{\ frac {k} {2}} \ oikea)+1 & k {\ text {even}}, \\ 8 \ cdot 2 ^{k} -6 \ cdot 2^{(k+1)/2}+1 & k {\ text {odd}} \ end {tapauksissa}}}$	${\ displaystyle 1,5,19,41,109, \ ldots}$	${\ displaystyle O \ vasen (N^{\ frac {4} {3}} \ oikea)}$	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}} \ oikea \ rfloor -1 \ right \ rfloor, \ ldots, 1}$	Tuntematon	Gonnet & Baeza-Yates , 1991
A108870	${\ displaystyle \ left \ lceil {\ frac {1} {5}} \ left (9 \ cdot \ left ({\ frac {9} {4}} \ right)^{k-1} -4 \ right) \ oikea \ rceil}$	${\ displaystyle 1,4,9,20,46,103, \ ldots}$	Tuntematon	Tokuda, 1992
A102549	Tuntematon (kokeellisesti johdettu)	${\ displaystyle 1,4,10,23,57,132,301,701}$	Tuntematon	Ciura, 2001

Kun binääriesityksen N sisältää useita peräkkäisiä nollia, Shellsort käyttäen Shellin alkuperäinen aukko sekvenssi tekee Θ ( N ² ) vertailut pahimmassa tapauksessa. Esimerkiksi tämä tapaus esiintyy N: lle, joka on yhtä suuri kuin kaksi voimaa, kun mediaania suurempia ja pienempiä elementtejä on pariton ja parillinen, vastaavasti, koska niitä verrataan vasta viimeisellä siirtymällä.

Vaikka Prattin versio on monimutkaisempi kuin O ( N  log  N ), joka on optimaalinen vertailulajeille, Prattin versio soveltuu lajitteluverkkoihin ja sillä on sama asymptoottinen portin monimutkaisuus kuin Batcherin bitonilajittelulla .

Gonnet ja Baeza-Yates havaitsivat, että Shellsort tekee keskimäärin vähiten vertailuja, kun peräkkäisten aukkojen suhde on suunnilleen 2,2. Siksi niiden sekvenssi suhteella 2.2 ja Tokudan sekvenssi suhteella 2,25 osoittautuvat tehokkaiksi. Ei kuitenkaan tiedetä, miksi näin on. Sedgewick suosittelee sellaisten aukkojen käyttämistä, joilla on pienimmät suurimmat yhteiset jakajat tai jotka ovat pareittain kopioituja .

Vertailujen keskimääräisen määrän osalta Ciuran sekvenssillä on tunnetuin suorituskyky; aukkoja 701: stä ei määritetty, mutta sekvenssiä voidaan edelleen pidentää rekursiivisen kaavan mukaisesti . ${\ displaystyle h_ {k} = \ lfloor 2.25h_ {k-1} \ rfloor}$

Tokudan sekvenssi, joka määritellään yksinkertaisella kaavalla , missä , voidaan suositella käytännön sovelluksiin. ${\ displaystyle h_ {k} = \ lceil h '_ {k} \ rceil}$${\ displaystyle h '_ {k} = 2.25h' _ {k-1} +1}$${\ displaystyle h '_ {1} = 1}$

Jos syötteen enimmäiskoko on pieni, kuten voi tapahtua, jos Shellsortia käytetään pienissä alijoukoissa toisessa rekursiivisessa lajittelualgoritmissa, kuten pikalähetys- tai yhdistämislajittelussa , on mahdollista taulukoittaa optimaalinen sekvenssi jokaiselle syöttökoolle.

Laskennallinen monimutkaisuus

Seuraava ominaisuus pätee: minkä tahansa h ₁ -lajitelman matriisin h ₂ -lajittelun jälkeen taulukko pysyy h ₁ -lajiteltuna. Jokainen h ₁ -sorted ja h ₂ -sorted matriisi on myös ( ₁ h ₁ + ₂ h ₂ ) -sorted, mitään negatiivisia kokonaislukuja ₁ ja ₂ . Shellsortin pahin tapaus liittyy siis Frobenius-ongelmaan : annetuille kokonaisluvuille h ₁ , ..., h _n, joiden gcd = 1, Frobenius-luku g ( h ₁ , ..., h _n ) on suurin kokonaisluku, joka ei ole edustettuina ₁ h ₁ + ... + _n h _n kanssa positiivinen kokonaisluku ₁ , ..., _n . Käyttämällä Frobenius-numeroiden tunnettuja kaavoja voimme määrittää Shellsortin pahimman monimutkaisuuden useille aukkosekvenssiluokille. Todistetut tulokset on esitetty yllä olevassa taulukossa.

Toimenpiteiden keskimääräisen määrän osalta mikään todistetuista tuloksista ei koske käytännön aukkosekvenssiä. Espelid laski tämän keskiarvon välille, jotka ovat kahden voimia . Knuth määritteli N -elementtimatriisin, jossa on kaksi aukkoa ( h , 1), keskimääräisen monimutkaisuuden olla . Tästä seuraa, että kaksikierroksinen Shellsort, jossa h = Θ ( N ^1/3 ), tekee keskimäärin O ( N ^5/3 ) vertailuja/käänteisiä/ajoaikaa. Yao löysi Shellsortin kolmiportaisen keskimääräisen monimutkaisuuden. Hänen tulostaan ​​tarkensivat Janson ja Knuth: Shellsortin aikana tehtyjen kolmen aukon ( ch , cg , 1) aikana tehtyjen vertailujen/inversioiden/ajoajan keskimääräinen lukumäärä ( ch , cg , 1), jossa h ja g ovat kopiokoneita, on ensimmäisellä kierroksella, toisella pass ja kolmannessa. ψ ( h , g ) viimeisessä kaavassa on monimutkainen funktio, joka on asymptoottisesti yhtä suuri kuin . Erityisesti kun h = Θ ( N ^7/15 ) ja g = Θ ( N ^1/5 ), keskimääräinen lajitteluaika on 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 \ vasen ((c-1) gh^{1/2} N \ oikea)+O \ vasen (c^{2} g^{3} h^{2} \ oikea)}$${\ displaystyle {\ sqrt {\ frac {\ pi h} {128}}} g+O \ vasen (g^{-1/2} h^{1/2} \ oikea)+O \ vasen (gh^ {-1/2} \ oikea)}$

Kokeiden perusteella arvellaan, että Shellsort kanssa Hibbard n aukko sekvenssi kulkee O ( N ^5/4 ) keskimääräinen aika, ja että Gonnet ja Baeza-Yates sekvenssin vaatii keskimäärin 0,41 N  ln  N  (ln ln  N  + 1/6 ) elementti liikkuu. Muille sekvensseille aiemmin esitettyjen operaatioiden keskimääräisen määrän arvioinnit epäonnistuvat, kun lajitellut taulukot sisältävät miljoonia elementtejä.

Alla olevassa kaaviossa esitetään elementtien vertailujen keskimääräinen lukumäärä Shellsortin eri muunnelmissa jaettuna teoreettisella alarajalla, eli log ₂ N !, Jossa sekvenssiä 1, 4, 10, 23, 57, 132, 301, 701 on laajennettu kaavan mukaan . ${\ displaystyle h_ {k} = \ lfloor 2.25h_ {k-1} \ rfloor}$

Sovellettaessa Kolmogorovin monimutkaisuuden teoriaa Jiang, Li ja Vitányi osoittivat seuraavan alarajan p -pass Shellsort -operaatioiden keskimääräisen lukumäärän/ käyntiajan järjestykselle: Ω ( pN ^{1+1/ p} ), kun p  ≤ log ₂ N ja Ω ( pN ), kun p  > log ₂ N . Siksi Shellsortilla on mahdollisuus suorittaa keskimääräinen aika, joka kasvaa asymptoottisesti N log N: n tavoin vain käytettäessä aukkosekvenssejä, joiden aukkojen määrä kasvaa suhteessa taulukon koon logaritmiin. On kuitenkin epäselvää, pystyykö Shellsort saavuttamaan tämän keskimääräisen tapauksen monimutkaisuuden asymptoottisen järjestyksen, joka on optimaalinen vertailulajeille. Alarajan paransi Vitányi jokaista ajokertojen ja missä . Tämä tulos tarkoittaa esimerkiksi Jiang-Li-Vitányin alarajaa all- pass -lisäyssekvensseille ja parantaa sitä alarajaa tietyille lisäyssekvensseille . Itse asiassa kaikki rajat (alempi ja ylempi), jotka tällä hetkellä tunnetaan keskimääräisestä tapauksesta, vastaavat tarkasti tätä alarajaa. Tämä antaa esimerkiksi uuden tuloksen, että Janson-Knuthin yläraja vastaa käytetyn lisäyssekvenssin tuloksena olevaa alarajaa, mikä osoittaa, että kolmen lisäyksen Shellsort käyttää tätä lisäyssekvenssiä vertailuja/käänteisiä/ajoaikaa. Kaavan avulla voimme etsiä lisäsekvenssejä, jotka tuottavat alempia rajoja, joita ei tunneta; esimerkiksi neljän jakson lisäyssekvenssi, jonka alaraja on suurempi kuin lisäyssekvenssillä . Alaraja muuttuu ${\ 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}).}$

Pahimman tapauksen monimutkaisuuteen mitään versiota Shellsort on korkeamman asteen: Plaxton, Poonen ja Suel osoitti, että se kasvaa vähintään yhtä nopeasti kuin . ${\ displaystyle \ Omega \ left (N \ left ({\ log N \ over \ log \ log N} \ right)^{2} \ right)}$

Sovellukset

Shellsort suorittaa enemmän toimintoja ja välimuistin missaussuhde on korkeampi kuin quicksort . Koska se voidaan toteuttaa käyttämällä vähän koodia ja ei käytä kutsupino , jotkut toteutukset qsort funktion C standardin kirjasto suunnattu sulautettujen järjestelmien käyttää sen sijaan quicksort. Shellsortia käytetään esimerkiksi uClibc -kirjastossa. Samoista syistä Shellsortia käytettiin aiemmin Linux -ytimessä .

Shellsort voi myös toimia introspektiivisen lajittelun alialgoritmina , lajitella lyhyitä aliryhmiä ja estää hidastumisen, kun rekursiosyvyys ylittää tietyn rajan. Tätä periaatetta käytetään esimerkiksi bzip2 -kompressorissa.

Katso myös

• Kampa lajitella

Viitteet

Bibliografia

• Knuth, Donald E. (1997). "Shellin menetelmä". Tietokoneohjelmoinnin taito. Osa 3: Lajittelu ja haku (2. painos). Reading, Massachusetts: Addison-Wesley. s. 83–95. ISBN 978-0-201-89685-5.
• Shellsortin ja siihen liittyvien algoritmien analyysi , Robert Sedgewick, Fourth European Symposium on Algorithms, Barcelona, ​​syyskuu 1996.

Ulkoiset linkit

• Animated lajittelualgoritmeja: Shell Lajittelu klo Wayback Machine (arkistoitu 10 maaliskuu 2015) - graafinen esittely
• Shellsort, aukot 5, 3, 1 unkarilaiseksi kansantanssiksi