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, 701Najboljše znano delilno zaporedje za Shellovo urejanje,
Č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
Kategorija:Algoritmi za urejanje podatkov Kategorija:1959 v znanosti