Shellovo urejanje

Iz Wikipedije, proste enciklopedije
Skoči na: navigacija, iskanje

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

Delovanje[uredi | uredi kodo]

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[uredi | uredi kodo]

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[1],

Č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[uredi | uredi kodo]

Č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[uredi | uredi kodo]

  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[uredi | uredi kodo]

Opombe in sklici[uredi | uredi kodo]