Shellovo urejanje: Razlika med redakcijama

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

Algoritem za hitrejše urejanje izrablja to, da algoritemurejanje navadnaz vstavljanjanavadnim vstavljanjem, skoraj urejena [[zaporedje|zaporedja]] uredi v času <math>O(n)</math>. Za delovanje potrebujemo delilno zaporedje(ang. {{jezik-en|gap sequence}}), ki pove v katerih stopnjah bomo urejali, npr. zČe delilnimizberemo zaporedjemdelilno 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, ...|...), natona koncu pa šeurejamo zvse vsakimelemente. indeksom (taTa stopnja je popolnoma enaka urejanju z navadnim vstavljanjem).

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

V tem primeru lahko zaporedje dopolnimo do željeneustrezne dolžine z rekurenčno enačbo:

: gap[i+1] = round(gap[i]*2.2);