Shellovo urejanje

Shellovo urejanje ali urejanje z vstavljanjem s padajočim prirastkom (angleško Shell sort) je algoritem za urejanje podatkov, ki ga je leta 1959 razvil Donald Shell. Algoritem je nadgradnja urejanja z navadnim vstavljanjem in je bil eden prvih odkritih algoritmov za urejanje, s časovno zahtevnostjo, manjšo od $O(n^{2})$.

Shellovo urejanje
Shellovo urejanje barvni algoritem palice
Osnovni podatki
Vrsta:	algoritem za urejanje podatkov
Podatkovna struktura:	tabela
Časovna zahtevnost
Zgornja meja zahtevnosti:	O(n2)
Spodnja meja zahtevnosti:	O(n log2 n)
Pričakovana zahtevnost:	odvisna od delilnega zaporedja
Prostorska zahtevnost
Prostorska zahtevnost:	O(n)

Delovanje

Algoritem za hitrejše urejanje izrablja to, da urejanje z navadnim vstavljanjem, skoraj urejena zaporedja uredi v času $O(n)$. Za delovanje potrebujemo delilno zaporedje(angleško 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 A102549): 1, 4, 10, 23, 57, 132, 301, 701,

Č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 $O(n^{2})$. Prostorska zahtevnost je $O(1)$, saj urejamo na mestu.

Psevdokoda

  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];
      }
    }
  }

Glej tudi

• Urejanje z navadnim vstavljanjem