Algoritem za Shellovo urejanje

Shellov urejanje deluje tako, da neurejeno vhodno tabelo veckrat razdelimo na nekaj "podtabel" in jih sortiramo (z navadnim vstavljanjem). Zaporedje, po katerem delimo tabelo, se računa po formuli:
h₁ = 1
h_n = 2h_{n − 1} + 1
V praksi to ponavadi pomeni zaporedje 1, 3, 7, ni pa vedno tako. Dobimo lahko podano tudi kakšno drugo zaporedje (recimo 1, 3, 5 za uporabo na papirju). Število iteracij dobimo s formulo , kjer je n število elementov za urejanje.

Tako dobimo podtabele ki jih sestavljajo elementi, ki so kN poziciji, kjer gre N od 1 do velikosti tabela, k, pa kolikor imamo pač tabel. Tako nato nad vsako izmed teh tabel naredimo navadno vstavanje. Nato postopek ponovimo na eno stopnjo manjši tabeli. Na koncu pa poženenmo še navadno vstavljanje

časovna analiza

To je v splošne prvi (zgodovinsko) algoritem, ki je porabi za urejanje manj kot n². In sicer ima casovno zahtevnost O(n^1.2).

Postopek

h(1,3,7) sedem podtabel

    1 2 3 4 5 6 7 1 2 3 4 5 6 7
   [*|$| | | | | |*|$| | | | | ]

uredimo * z navadnim vstavljanjem

   1 2 3 1 2 3 1 2 3 1 2 3
  [*| | |*| | |*| | |*| | | ]

 1 2 3  4 5 6 7 1  2  3  4 5  6  7  1 2  3 4
17 3 5 11 6 1 2 8 10 12 18 4 16 15 14 7 13 9
 8             14                  17         <-- 1. podtabela
   3               7                 10       <-- 2. podtabela
     5               12                 13    <-- 3. podtabela
        9              ...                ... <-- 4. podtabela

---

Zgornje zaporedje lahko uredimo tudi v:

   17  3  5 11  6  1  2

8 10 12 18 4 16 15

14 7 13 9

in nato sortiramo po stolpcih:

    8  3  5  9  4  1  2

14 7 12 11 6 16 15

17 10 13 18

(zaporedje lahko nato normalno prepisemo v vrstico)

8  3  5  9  4  1  2 14  7 12 11  6 16 15 17 10 13 18

---

 1 2 3 1 2 3 1  2 3  1  2 3  1  2  3  1  2  3
 8 3 5 9 4 1 2 14 7 12 11 6 16 15 17 10 13 18

Navadno vstavljanje:

 2 3 1 8 4 5 9 11 6 10 13 7 12 14 17 16 15 18

Nato se celotno zgornje zaporedje uredimo z navadnim vstavljanjem in dobimo urejeno zaporedje.

Poglejmo se koliko so elementi zamaknjeni od urejenega zaporedja.

• Zacetni zamik:

 17  3  5 11  6  1  2  8 10 12 18  4 16 15 14  7 13  9
 16 +1 +2 +7 +1 +5 +5 +0 +1 +2 +7 +8 +3 +1 +1 +9 +4 +9 = 75/8

• Koncni zamik:

  2  3  1  8  4  5  9 11  6 10 13  7 12 14 17 16 15 18
  1 +1 +2 +4 +1 +1 +2 +3 +3 +0 +2 +5 +1 +0 +2 +0 +2 +0 = 30/18