Shellsort algorithm

Shellsort algorithm (tsz. Shellsort algorithms)

1. (informatika) Shellsort egy rendezőalgoritmus, amely Don Shell nevéhez fűződik (1959). A beillesztéses rendezés (Insertion Sort) továbbfejlesztése: tetszőleges távolságú (gap-beli) elemeket “csomagokba” gyűjt és elő­rendez, így a tényleges beillesztéses rendezés már viszonylag kis tologatásokkal dolgozik, gyorsabban konvergálva.

1. Gap-sorozat választása: egy csökkenő sorozat, például ${\textstyle \lfloor n/2\rfloor ,\lfloor n/4\rfloor ,\dots ,1}$.
2. Minden gap-értékre (${\textstyle h}$) végrehajtunk egy ${\textstyle h}$-lépéses beillesztéses rendezést:
   • Vegyük sorra az indexeket ${\textstyle i=h,h+1,\dots ,n-1}$.
   • Az ${\textstyle A}$ elemet „kikapjuk”, és „előrébb” tologatjuk a már ${\textstyle h}$-részekre bontott szekvenciában, amíg a megfelelő helyre nem kerül.
3. Végül gap = 1-nél a hagyományos Insertion Sort fut, de az adatsor már közel rendezett, így gyors.

ShellSort(A):  
  gaps = gap_sequence(n)       // pl. n/2, n/4, …, 1
  for each h in gaps:          
    for i = h to n-1:
      temp = A
      j = i
      while j ≥ h and A > temp:
        A = A
        j = j - h
      A = temp

A teljesítmény leginkább a gap-sorozattól függ:

Sorozat	Jellemző futásidő
Shell eredeti: ${\textstyle n/2^{k}}$	${\textstyle O(n^{2})}$
Hibbard: ${\textstyle 2^{k}-1}$	${\textstyle O(n^{3/2})}$
Pratt: ${\textstyle 2^{i}3^{j}}$	${\textstyle O(n\log ^{2}n)}$
Sedgewick	${\textstyle O(n^{4/3})}$ vagy jobb
Tokuda, Ciura stb.	gyakorlati leggyorsabb

A leggyakrabban használt gyakorlatban a Ciura-sorozat (1, 4, 10, 23, 57, 132, …) kiváló eredményeket ad.

• Átlagos futásidő: gap-sorozattól függően ${\textstyle O(n^{4/3})}$ és ${\textstyle O(n\log ^{2}n)}$ körül.
• Legrosszabb eset: általában ${\textstyle O(n^{2})}$, de megfelelő gap-sorozattal lejjebb szorítható.
• További előnyök:
  • In-place: nem igényel extra memóriát.
  • Stabilitás: nem stabil (azonos értékek sorrendje változhat).
  • Egyszerű implementáció és jó gyakorlati sebesség közepes méretű tömbökön.

• Közepes méretű tömbök rendezésére (nagy ${\textstyle n}$-re már mergesort vagy heapsort jobb).
• Ha memória-korlátozott környezetben in-place, stabilitás nélkül.
• Beágyazott rendszerekben, ahol egyszerű kódra és kis helyigényre van szükség.

A Shellsort egy intelligens beillesztéses rendezés gap-beli elő­rendezéssel, amely tetszőleges gap-sorozatokkal testre szabható, és gyakorlati alkalmazásokban—kis- és közepes méretekben—kiemelkedő hatékonyságot nyújt.

• Shellsort algorithm - Szótár.net (en-hu)
• Shellsort algorithm - Sztaki (en-hu)
• Shellsort algorithm - Merriam–Webster
• Shellsort algorithm - Cambridge
• Shellsort algorithm - WordNet
• Shellsort algorithm - Яндекс (en-ru)
• Shellsort algorithm - Google (en-hu)
• Shellsort algorithm - Wikidata
• Shellsort algorithm - Wikipédia (angol)