Shellovo urejanje
Shellovo urejanje ali urejanje z vstavljanjem s padajočim prirastkom () 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 .

Delovanje 

Algoritem za hitrejše urejanje izrablja to, da urejanje z navadnim vstavljanjem, skoraj urejena zaporedja uredi v času . Za delovanje potrebujemo delilno zaporedje(), 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 :
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 . Prostorska zahtevnost je , 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

Opombe in sklici 

Algoritmi za urejanje podatkov
1959 v znanosti
Shellovo urejanje ali urejanje z vstavljanjem s padajočim prirastkom ( ) je algoritem za urejanje podatkov , ki ga je letarazvil Donald Shell . Algoritem je nadgradnja urejanja z navadnim vstavljanjem in je bil eden prvih odkritih algoritmov za urejanje , s časovno zahtevnostjo , manjšo od \ . Delovanje Algoritem za hitrejše urejanje izrablja to , da urejanje z navadnim vstavljanjem , skoraj urejena zaporedja uredi v času \ . Za delovanje potrebujemo delilno zaporedje ( ) , ki pove v katerih stopnjah bomo urejali . Če izberemo delilno zaporedje bomo najprej uredili podtabele z vsakim sedmim indeksom v tabeli ( podtabela1: \ . . . |podtabela2 : \ . . . |podtabela3 : \ . . . | . . . ) , nato podtabele z vsakim tretjim indeksom ( podtabela1: \ . . . |podtabela2 : \ . . . | . . . ) , 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 ampak je hitrost algoritma zelo odvisna od izbire delilnega zaporedja . Najbolj optimalno zaporedje , ki je znano , je sestavil Marcin Ciura in se glasi \ : 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 Časovna zahtevnost algoritma je odvisna od delilnega zaporedja in za povprečni primer ni znana , je pa navzgor omejena z \ . Prostorska zahtevnost je , saj urejamo na mestu . Psevdokoda for( p = length ( gap ) - 1; p >= p - - ) { for( i = 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 Opombe in sklici Algoritmi za urejanje podatkov 1959 v znanosti