Shelli sortimine

Shelli sortimine

Shelli sortimine sammudega 23, 10, 4, 1
Algoritmi liik	Sortimisalgoritm
Ajaline keerukus halvimal juhul	O(n2) (halvima sammujadaga) O(n log2n) (parima teadaoleva sammujadaga)
Ajaline keerukus keskmiselt	sõltub sammude jadast
Ajaline keerukus parimal juhul	O(n log n) (enamus sammujadasid) O(n log2n)
Mahuline keerukus	О(n)

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.

	a1	a2	a3	a4	a5	a6	a7	a8	a9	a10	a11	a12
Algne loend	62	83	18	53	07	17	95	86	47	69	25	28
5-sorditud	17	28	18	47	07	25	83	86	53	69	62	95
3-sorditud	17	07	18	47	28	25	69	62	53	83	86	95
1-sorditud	07	17	18	25	28	47	53	62	69	83	86	95

Esimesel läbimisel sorditakse pistemeetodil alamloendid, mille elementide indeksid algses loendis erinevad 5 võrra: (a₁, a₆, a₁₁), (a₂, a₇, a₁₂), (a₃, a₈), (a₄, a₉), (a₅, a₁₀). Näiteks on alamloend (a₁, a₆, a₁₁) ehk (62, 17, 25) pärast sortimist (17, 25, 62). Järgmisel läbimisel sorditakse alamloendid (a₁, a₄, a₇, a₁₀), (a₂, a₅, a₈, a₁₁), (a₃, a₆, a₉, a₁₂). Viimasel läbimisel sorditakse kogu loend (a₁,..., a₁₂) 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.

Jada üldliige (k ≥ 1)	Konkreetsed sammud	Halvima juhu ajaline keerukus	Autor ja avaldamise aasta
$\left\lfloor {\frac {N}{2^{k}}}\right\rfloor$	$\left\lfloor {\frac {N}{2}}\right\rfloor ,\left\lfloor {\frac {N}{4}}\right\rfloor ,\ldots ,1$	$\Theta \left(N^{2}\right)$ [nt N = 2p korral]	Shell, 1959
$2\left\lfloor {\frac {N}{2^{k+1}}}\right\rfloor +1$	$2\left\lfloor {\frac {N}{4}}\right\rfloor +1,\ldots ,3,1$	$\Theta \left(N^{\frac {3}{2}}\right)$	Frank & Lazarus, 1960
$2^{k}-1$	$1,3,7,15,31,63,\ldots$	$\Theta \left(N^{\frac {3}{2}}\right)$	Hibbard, 1963
$2^{k}+1$, alates arvust 1	$1,3,5,9,17,33,65,\ldots$	$\Theta \left(N^{\frac {3}{2}}\right)$	Papernov & Stasevich, 1965
Järjestikused arvud kujul $2^{p}3^{q}$	$1,2,3,4,6,8,9,12,\ldots$	$\Theta \left(N\log ^{2}N\right)$	Pratt, 1971
${\frac {3^{k}-1}{2}}$, mitte suurem kui $\left\lceil {\frac {N}{3}}\right\rceil$	$1,4,13,40,121,\ldots$	$\Theta \left(N^{\frac {3}{2}}\right)$	Knuth, 1973, eeskujuks Pratt, 1971
${\begin{aligned}&\prod \limits _{I}a_{q},{\hbox{kus}}\\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}}$	$1,3,7,21,48,112,\ldots$	$O\left(N^{1+{\sqrt {\frac {8\ln \left(5/2\right)}{\ln(N)}}}}\right)$	Incerpi & Sedgewick, 1985, Knuth
$4^{k}+3\cdot 2^{k-1}+1$, alates arvust 1	$1,8,23,77,281,\ldots$	$O\left(N^{\frac {4}{3}}\right)$	Sedgewick, 1982
${\begin{cases}9\left(2^{k}-2^{\frac {k}{2}}\right)+1&k{\text{ on paaris}},\\8\cdot 2^{k}-6\cdot 2^{(k+1)/2}+1&k{\text{ on paaritu}}\end{cases}}$	$1,5,19,41,109,\ldots$	$O\left(N^{\frac {4}{3}}\right)$	Sedgewick, 1986
$h_{k}=\max \left\{\left\lfloor {\frac {5h_{k-1}}{11}}\right\rfloor ,1\right\},h_{0}=N$	$\left\lfloor {\frac {5N}{11}}\right\rfloor ,\left\lfloor {\frac {5}{11}}\left\lfloor {\frac {5N}{11}}\right\rfloor \right\rfloor ,\ldots ,1$	Teadmata	Gonnet & Baeza-Yates, 1991
$\left\lceil {\frac {1}{5}}\left(9\cdot \left({\frac {9}{4}}\right)^{k-1}-4\right)\right\rceil$	$1,4,9,20,46,103,\ldots$	Teadmata	Tokuda, 1992
Teadmata (eksperimentaalselt leitud)	$1,4,10,23,57,132,301,701$	Teadmata	Ciura, 2001

Kui arvu N kahendesituses esineb palju järjestikuseid nulle, tehakse sortimisel Shelli originaalse sammujadaga halvimal juhul Θ(N²) 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 $h_{k}=\lfloor 2.25h_{k-1}\rfloor$.

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.