Shellsort algorithm

Angol

Főnév

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. Algoritmus vázlata

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[i]}$ 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[0..n-1]):  
  gaps = gap_sequence(n)       // pl. n/2, n/4, …, 1
  for each h in gaps:          
    for i = h to n-1:
      temp = A[i]
      j = i
      while j ≥ h and A[j-h] > temp:
        A[j] = A[j-h]
        j = j - h
      A[j] = temp

---

2. Gap-sorozatok

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.

---

3. Teljesítmény és jellemzők

• Á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.

---

4. Mikor érdemes használni?

• 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.

---

Összefoglaló

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.

További információk

• 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)