Shellovo urejanje: Razlika med redakcijama
Izbrisana vsebina Dodana vsebina
m popravil povezavo |
m malo uredil tekst |
||
Vrstica 1:
'''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>.
== Delovanje ==
Algoritem za hitrejše urejanje izrablja to, da
== Delilna zaporedja ==
Uporabimo lahko katerokoli naraščajoče zaporedje, ki se začne s
Najbolj optimalno zaporedje, ki je znano, je sestavil [[Marcin Ciura]] in se glasi {{OEIS|id=A102549}}:
Vrstica 13:
Č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
: gap[i+1] = round(gap[i]*2.2);
== Zahtevnost ==
|