Ideea metodei este de a compara elementele grupate dintr-o secvență care se află la o anumită distanță una de cealaltă. Inițial, această distanță este d sau N / 2, unde N este numărul total de elemente. În prima etapă, fiecare grup cuprinde două elemente situate la o distanță N / 2 unele de altele; ele sunt comparate între ele și, dacă este necesar, sunt schimbate. În etapele următoare se efectuează și verificarea și schimbul, dar distanța d este redusă cu d / 2, iar numărul de grupuri, respectiv, scade. Treptat, distanța dintre elemente scade, iar pentru d = 1 trecerea prin matrice are loc ultima dată.
Apoi, un exemplu de secvență de numere întregi, arată procesul de sortare a unei matrice prin metoda Shell. Pentru confort și claritate, elementele unui grup sunt evidențiate în aceeași culoare.
Prima valoare corespunzătoare distanței d este 10/2 = 5. La fiecare pas este redus la jumătate. Elementele care aparțin aceluiași grup sunt comparate și dacă valoarea oricărui element care este la stânga celei cu care este comparat se dovedește a fi mai mare (sortarea în ordine crescătoare), atunci ele schimbă locurile. Astfel elementele prin permutări intragrup se transformă treptat în pozițiile lor, iar în ultima etapă (d = 1) sortarea este redusă la trecerea unui grup, incluzând toate elementele N ale matricei. În același timp, numărul schimburilor necesare este foarte mic.
Codul programului C ++:
Codul programului pe Pascal:
program ShellSorting;
utilizează CRT;
tip massiv = matrice # 91; 1. 100 # 93; de intreg;
var i. j. n. d. conta. întreg;
A. masiv;
procedura Shell # 40; A. masiv; n. întreg # 41; ;
începe
d: = n;
d: = d div 2;
în timp ce # 40; d> 0 # 41; face
începe
pentru i: = 1 la n - d
începe
j: = i;
în timp ce # 40; # 40; j> 0 # 41; și # 40; A # 91; j # 93;> A # 91; j + d # 93; # 41; # 41; face
începe
număr: = A # 91; j # 93; ;
A # 91; j # 93; : = A # 91; j + d # 93; ;
A # 91; j + d # 93; : = număr;
j: = j-1;
se încheie;
se încheie;
d: = d div 2;
se încheie;
writeln;
pentru i: = 1 la n nu scrie # 40; ''. A # 91; eu # 93; # 41; ;
se încheie;
începe
scrie # 40; "Dimensiunea matricei>" # 41; ; citit # 40; n # 41; ;
pentru i: = 1 până la n
începeți să scrieți # 40; i. 'Element>' # 41; ; readln # 40; A # 91; eu # 93; # 41; ; se încheie;
scrie # 40; "Matrice rezultată:" # 41; ;
coajă # 40; A. n # 41; ;
end.
Sortarea Schella este inferioară eficienței sortării rapide, dar câștigă prin inserții de sortare. Comparați viteza acestor trei algoritmi utilizând tabelul următor.
Articole similare
-
Sortarea și filtrarea în Excel utilizând exemplul unei baze de date a clienților
-
Lista cărților și a altor lucrări ale sorții lui Fedor Michailovici Dostoievski
Trimiteți-le prietenilor: