Ogled vira Shellovo urejanje

{{Infopolje Algoritem
|slika=[[Slika:Shell sorting algorithm color bars.svg|300px]]
|napis=Shellovo urejanje barvni algoritem palice
|vrsta=[[Algoritmi_za_urejanje_podatkov|algoritem za urejanje podatkov]]
|struktura=[[Tabela_(računalništvo)|tabela]]
|worst-time=O(''n''<sup>2</sup>)
|average-time=odvisna od delilnega zaporedja
|best-time=O(''n'' log<sub>2</sub> ''n'')
|space=O(''n'')
}}
'''Shellovo urejanje''' ali '''urejanje z vstavljanjem s padajočim prirastkom''' ({{jezik-en|Shell sort}}) je [[algoritmi za urejanje podatkov|algoritem za urejanje podatkov]], ki ga je leta [[1959]] razvil [[Donald Shell]]. Algoritem je nadgradnja [[Urejanje z navadnim vstavljanjem|urejanja z navadnim vstavljanjem]] in je bil eden prvih odkritih algoritmov za urejanje, s časovno zahtevnostjo, manjšo od <math>O(n^2)</math>.

== Delovanje ==

Algoritem za hitrejše urejanje izrablja to, da urejanje z navadnim vstavljanjem, skoraj urejena [[zaporedje|zaporedja]] uredi v času <math>O(n)</math>. Za delovanje potrebujemo delilno zaporedje({{jezik-en|gap sequence}}), ki pove v katerih stopnjah bomo urejali. Če izberemo delilno zaporedje (1, 3, 7), bomo najprej uredili podtabele z vsakim sedmim indeksom v tabeli (podtabela1: 0, 7, 14, ...|podtabela2: 1, 8, 15, ...|podtabela3: 2, 9, 16, ...|...), nato podtabele z vsakim tretjim indeksom (podtabela1: 0, 3, 6, ...|podtabela2: 1, 4, 7, ...|...), na koncu pa urejamo vse elemente. Ta stopnja je popolnoma enaka urejanju z navadnim vstavljanjem.

== Delilna zaporedja ==

Uporabimo lahko katerokoli naraščajoče zaporedje, ki se začne s številom 1, ampak je hitrost algoritma zelo odvisna od izbire delilnega zaporedja.

Najbolj optimalno zaporedje, ki je znano, je sestavil [[Marcin Ciura]] in se glasi {{OEIS|id=A102549}}:
1, 4, 10, 23, 57, 132, 301, 701<ref>[http://www.research.att.com/~njas/sequences/A102549 Najboljše znano delilno zaporedje za Shellovo urejanje]</ref>,

Če imamo tabelo, ki je dolga več kot nekaj tisoč elementov začne učinkovitost algoritma padati, saj na začetku algoritma spet urejamo dolge neurejene tabele.
V tem primeru lahko zaporedje dopolnimo do ustrezne dolžine z rekurenčno enačbo:
: gap[i+1] = round(gap[i]*2.2);

== Zahtevnost ==

[[Časovna zahtevnost]] algoritma je odvisna od delilnega zaporedja in za povprečni primer ni znana, je pa navzgor omejena z <math>O(n^2)</math>. [[Prostorska zahtevnost]] je <math>O(1)</math>, saj urejamo na mestu.

== Psevdokoda ==
<source lang="c">
  for(p = length(gap)-1; p >= 0; p--) {
    for(i = 0; i < length(tabela)-1; i++) {
      j = i+gap[p];

      while((j >= gap[p])&&(j < length(tabela))&&(tabela[j] < tabela[j-gap[p]])) {
        zamenjaj(tabela[j], tabela[j-gap[p]]);
        j-=gap[p];
      }
    }
  }
</source>
== Glej tudi ==

* [[Urejanje z navadnim vstavljanjem]]

== Opombe in sklici ==
{{opombe}}

[[Kategorija:Algoritmi za urejanje podatkov]]
[[Kategorija:1959 v znanosti]]