Shelli sortimine

Shelli sortimine (ka väheneva sammu meetod) on sortimisalgoritm, mis töötab kohapeal (s.t. ei vaja abiandmestruktuure) ja põhineb elementide võrdlusel. Shelli sortimisalgoritmi vaadeldakse tavaliselt pistemeetodi variatsioonina, kus võrreldakse ja vahetatakse ka üksteisest kaugel asuvaid elemente.

Algoritmi käigus sorditakse esmalt elemendid, mis asuvad üksteisest suure fikseeritud sammu kaugusel, seejärel vähendatakse järk-järgult sorditavate elementide vahelist sammu. Suure sammuga alustamine võimaldab mõned elemendid viia oma õigele positsioonile kiiremini kui ainult kõrvuti asuvate elementide vahetamine.

Algoritmi esimese versiooni avaldas Donald Shell 1959. aastal.

 Kirjeldus 
Shelli sortimise idee seisneb loendi elementide ümberpaigutamises nii, et võttes mistahes positsioonist alustades iga h-nda elemendi, saadakse sorditud alamloend. Sel juhul öeldakse, et loend on h-sorditud. Suurte h väärtustega alustamine võimaldab liigutada elementide kaugetele positsioonidele, vähendades kiiresti valejärjestusi. Kui loend on k-sorditud mingi täisarvu k < h korral, siis loend jääb ka h-sordituks. Vähendades sammu h arvuni 1, saadakse tulemuseks alati sorditud loend.

Alljärgnev on näide Shelli sortimisest sammudega 5, 3 ja 1.
a1a2a3a4a5a6a7a8a9a10a11a12Algne loend6283185307179586476925285-sorditud1728184707258386536962953-sorditud1707184728256962538386951-sorditud071718252847536269838695
Esimesel läbimisel sorditakse pistemeetodil alamloendid, mille elementide indeksid algses loendis erinevad 5 võrra: (a1, a6, a11), (a2, a7, a12), (a3, a8), (a4, a9), (a5, a10). Näiteks on alamloend (a1, a6, a11) ehk (62, 17, 25) pärast sortimist (17, 25, 62). Järgmisel läbimisel sorditakse alamloendid (a1, a4, a7, a10), (a2, a5, a8, a11), (a3, a6, a9, a12). Viimasel läbimisel sorditakse kogu loend (a1,..., a12) tavalise pistemeetodiga.

Näide illustreerib, kuidas Shelli sortimisel on alamloendid algul lühikesed ja hiljem pikad, kuid peaaegu sorditud. Mõlemal juhul töötab tavaline pistemeetod efektiivselt.

Shelli sortimine ei ole stabiilne: võrdsete elementide korral võib nende omavaheline järjestus tulla erinev. Shelli sortimisalgoritm on adaptiivne ehk selle tööaeg on lühem loenditel, mis on juba osaliselt sorditud.

 Pseudokood 
Koodis on kasutatakse Marcin Ciura sammude jada ja sisemise sortimismeetodina pistemeetodit.
# Olgu sorditavaks loendiks a[0...n-1].
gaps = [701, 301, 132, 57, 23, 10, 4, 1]

# Alustame suurima sammuga ja lõpetame sammuga 1.
foreach (gap in gaps)
{
    # Sordime üksteisest käesoleva sammu kaugusel asuvad elemendid.
    # Esimese sammu elemendid a[0..gap-1] on juba sammu järgi sorditud.
    # Lisame ühe elemendi kaupa, kuni kogu loend on sammu järgi sorditud.
    for (i = gap; i < n; i += 1)
    {
        # Lisame a[i] sammuga sorditud elementide hulka.
        # Salvestame a[i] abimuutujasse temp, et vabastada positsioon i.
        temp = a[i]
        # Nihutame varasemaid sammuga sorditud elemente, kuni leiame a[i] õige positsiooni.
        for (j = i; j >= gap and a[j - gap] > temp; j -= gap)
        {
            a[j] = a[j - gap]
        }
        # Paneme abimuutuja (originaalse a[i]) õigele positsioonile.
        a[j] = temp
    }
}

 Sammujadad 
Shelli sortimisalgoritmi ajaline keerukus sõltub valitud sammupikkuste jadast. Tõestatult parimat võimalikku sammujada ei ole leitud. Iga sammujada, mis lõpeb sammuga 1, annab Shelli sortimise tulemuseks korrektselt sorditud loendi.

Alljärgnev tabel võrdleb levinumaid seni avaldatud sammujadasid. Mõned neist on kasvavad lõpmatud jadad, mille elemendid, mis on väiksemad kui N, tuleb võtta vastupidises (kahanevas) järjekorras.

 {| class="wikitable"
!Jada üldliige (k ≥ 1)
!Konkreetsed sammud
!Halvima juhu ajaline keerukus
!Autor ja avaldamise aasta
|-
|
|
| [nt N = 2p korral]
|Shell, 1959
|-
|
|
|
|Frank & Lazarus, 1960
|-
|
|
|
|Hibbard, 1963
|-
|, alates arvust 1
|
|
|Papernov & Stasevich, 1965
|-
|Järjestikused arvud kujul 
|
|
|Pratt, 1971
|-
|, mitte suurem kui 
|
|
|Knuth, 1973, eeskujuks Pratt, 1971
|-
|
|
|
|Incerpi & Sedgewick, 1985, Knuth
|-
|, alates arvust 1
|
|
|Sedgewick, 1982
|-
|
|
|
|Sedgewick, 1986
|-
|
|
|Teadmata
|Gonnet & , 1991
|-
|
|
|Teadmata
|Tokuda, 1992
|-
|Teadmata (eksperimentaalselt leitud)
|
|Teadmata
|Ciura, 2001
|}

Kui arvu N kahendesituses esineb palju järjestikuseid nulle, tehakse sortimisel Shelli originaalse sammujadaga halvimal juhul Θ(N2) võrdlust. Selline juht ilmneb näiteks siis, kui N on võrdne arvu 2 mingi astmega ja mediaanist suuremad elemendid on paaritutel positsioonidel ning väiksemad paaris positsioonidel, kuna siis võrreldakse neid alles viimasel läbimisel.

Keskmise võrdluste arvu poolest on teadaolevalt parima jõudlusega Ciura jada, kus sammupikkused üle 701 saab välja arvutada üldvalemiga .

 Rakendused 

Shelli sortimine teeb rohkem võrdlusi ja sellel on suurem vahemälu möödalask kui kiirsortimisel, kuid selle implementatsioon on lühike ja see ei kasuta kutsepinu. Seetõttu on Shelli sortimine kasutusel mõnes qsort funktsiooni implementatsioonis C standardteegis, mis on suunatud manussüsteemidele. Sarnastel põhjustel oli Shelli sortimine varem kasutusel Linuxi kernelis. Shelli sortimist võib kasutada introsort algoritmis, et sortida lühikesi alamloendeid ja vältida algoritmi aeglustumist, kui rekursioon saavutab teatud sügavuse. Sel põhimõttel töötab näiteks bzip2 kompressor.

 Viited 

Kategooria:Sortimisalgoritmid