shell sort
Az az elképzelés, a módszer csoportokra osztjuk összehasonlítása szekvencia elemek, amelyek egymástól bizonyos távolságra. Kezdetben, a d távolság egyenlő vagy N / 2, ahol n - teljes száma elemek. Az első lépésben, minden egyes csoport magában foglalja a két elem egymástól azonos távolságra, a távolság N / 2; összehasonlítják őket egymással, és ha szükséges, módosítsa helyeken. Az ezt követő lépések történnek a vizsgálati és a csere, de a d távolság csökken d / 2, és a csoportok száma csökken megfelelően. Fokozatosan csökken a távolság a elemek, és d = 1 áthaladnak a tömb történik utoljára.
Ezután, egy példa szekvenciát egész számok, eljárást szemlélteti válogatás tömb Shell által. Egyszerűség kedvéért, az elemek egyik csoport osztják az azonos színű.
Az első érték megfelel annak a távolságnak d egyenlő 10/2 = 5. Minden lépésnél, akkor a felére csökken. Tartozó elemek ugyanazon csoporthoz képest, és ha az érték minden elem, álló balra, amelyhez hasonlítják, hosszabb (növekvő sorrend) mivel azok felcserélődnek. Így, intra-permutáció elemek fokozatosan a helyükre, és az utolsó lépés a (d = 1) redukálódik a rendezési áthaladását az azonos csoportba, beleértve az összes N tömbelemek. Ebben az esetben a szükséges számú cserék nagyon alacsony.
programkód C ++:
programkód Pascal:
programot ShellSorting;
használja crt;
típusú massiv = array # 91; 1. 100 # 93; Az egész szám;
var i. j. n. d. számítanak. integer;
A. massiv;
eljárás Shell # 40; A. massiv; n. egész szám # 41; ;
kezdődik
d: = N;
d: = d div 2;
míg # 40; d> 0 # 41; csinál
kezdődik
i: = 1-től n - d do
kezdődik
J: = i;
míg # 40; # 40; j> 0 # 41; és # 40; A # 91; j # 93;> A # 91; j + d # 93; # 41; # 41; csinál
kezdődik
száma: = A # 91; j # 93; ;
A # 91; j # 93; : = A # 91; j + d # 93; ;
A # 91; j + d # 93; : = Count;
j: = j - 1;
végén;
végén;
d: = d div 2;
végén;
writeln;
i: = 1-től n-do levelet # 40; ''. A # 91; én # 93; # 41; ;
végén;
kezdődik
ír # 40; „A méret a tömb>” # 41; ; olvas # 40; n # 41; ;
i: = 1-től n-do
kezdődik write # 40; i. 'Element>' # 41; ; readln # 40; A # 91; én # 93; # 41; ; végén;
ír # 40; „Az így kapott tömb” # 41; ;
héj # 40; A. N # 41; ;
végén.
Shell rendezés olyan hatékony, mint a gyors rendezés, de nyer a válogatás betétekkel. Hasonlítsa össze a sebesség három algoritmusok segítségével lehetséges az alábbi táblázatban.