Metode de sortare ale elementelor unui vector

1. Tema referatului

1.1 Metode de sortare ale elementelor unui vector

Proiectul realizeaza implementarea unor tehnici cunoscute prin care se poate ordona un vector de numere intregi, crescator sau descrescator, in functie de optiunea utilizatorului. In practica, problemele de sortare apar sub forma ordonarii informatiilor memorate intr-o structura de tip baza de date, cele mai simple structuri de date fiind vectorii, listele si arborii. Informatiile trebuie sortate in functie de necesitatile utilizatorului si prezentate acestuia in forma coerenta ceruta, in vederea operatiilor ulterioare ce vor fi executate asupra lor. Un exemplu practic il poate reprezenta gestiunea unui magazin de articole vestimentare. Fiecare articol este retinut intr-o structura de date, prin numeroasele informatii despre acesta(denumire, pret, numar de articole de acelasi tip disponibile in stoc, etc.). In acest caz particular poate aparea necesitatea de a ordona articolele vestimentare dupa pret, sau dupa numarul de articole ramase in stoc, pentru un eventual inventar. Proiectul se va ocupa insa de ordonarile simple pe vector de elemente intregi, deci un singur camp de informatie de ordonat. Diversele tehnici prezentate sunt diferite prin complexitate si grad de eficienta, de aici si nevoia de a alege metoda cea mai potrivita pentru o situatie data.

Metodele de sortare sunt, bineinteles, variate, iar proiectul le trateaza doar pe cele mai folosite dintre acestea.

Aplicatia care pune la dispozitie tehnicile ce vor fi discutate in continuare, a fost scrisa in limbajul de programare Pascal, si foloseste un meniu pentru comunicarea cu utilizatorul. Fisierul executabil al aplicatiei se numeste Sortari.exe.

2. Consideratii teoretice

2.1 Descrierea metodelor de sortare utilizate de aplicatie

In continuare, vor fi descrise tehnicile de sortare implementate in limbajul Pascal, prezentand algoritmul lor de functionare. Fiecare metoda discuta ordonarea crescatoare a elementelor vectorului, devreme ce ordonarea descrescatoare nu difera ca pasi de parcurs. Aplicatia pune la dispozitie, totusi, ambele posibilitati de a ordona un vector, prin implementarea a doua proceduri(pentru ordonare crescatoare si descrescatoare) pentru fiecare metoda in parte.

2.1.1 Sortarea prin insertie directa.

Algoritmii de insertie presupun parcurgerea sirului(vectorului) si insertia fiecarui element in subsirul ordonat creat anterior din elementele precedente.

Fie i cu proprietatea a₁<a₂<<a_i-1. Trebuie sa inseram pe a_i in subsirul anterior. Pentru aceasta va trebui sa comparam pe rand pe a_i cu a_i-1, a_i-2, pana cand vom gasi un element a_j cu a_j<=a_i. Adica va trebui parcurs sirul a­₁<a₂ <a_i-1 de la dreapta catre stanga pana cand un element a_j<=a_i. Daca acest element nu exista oprirea se va face pe primul element al sirului adica pe a₁. Vom insera pe a_i dupa a­_j.

Procedura in limbajul Pascal care realizeaza operatiile descrise mai sus este:

procedure SortInsDir_C(var A:vector; n:integer);

var x,i,j:integer;

begin

for i:=2 to n do

begin

x:=A[i];

j:=i-1;

while (x<A[j]) and (j<>0) do

begin

A[j+1]:=A[j];

j:=j-1;

end;

A[j+1]:=x;

end;

end;

2.1.2 Sortarea prin insertie binara.

Algoritmul este similar cu cel anterior doar ca locul in care se face inserarea elementului a_i se cauta printr-un algoritm de cautare binara.

Procedura SortInsBin_C exemplifica acest algoritm:

procedure SortInsBin_C(var A:vector; n:integer);

var x,i,j,s,d,m:integer;

begin

for i:=2 to n do

begin

x:=A[i];

s:=1;

d:=i-1;

while (s<=d) do

begin

m:=(s+d) div 2;

if x<A[m] then d:=m-1

else s:=m+1;

end;

for j:=i-1 downto s do

A[j+1]:=A[j];

A[s]:=x;

end;

end;

2.1.3. Sortarea prin numarare.

Acest algoritm numara pentru fiecare element a_i cate elemente mai mici strict decat el exista. Numerele obtinute le vom memora intr-un vector notat C. Pe baza acestuia vom rearanja elementele vectorului A intr-un alt vector notat B. In final vectorul B va fi copiat in A, deoarece B contine elementele lui A ordonate crescator. Pentru aceasta metoda s-a presupus ca elementele vectorului A sunt distincte.

Procedura SortNum_C care implementeaza algoritmul:

procedure SortNum_C(var A:vector; n:integer; B,C:vector);

var i,j:integer;

begin

for i:=1 to n do

C[i]:=1;

for j:=2 to n do

for i:=1 to j-1 do

if A[i]<A[j] then C[j]:=C[j]+1

else C[i]:=C[i]+1;

for i:=1 to n do

B[C[i]]:=A[i];

for i:=1 to n do

A[i]:=B[i];

end;

2.1.4. Sortarea prin selectie.

Acest algoritm are la baza problema selectiei, aceasta presupunand ca, avand un vector A=(a₁, a₂, , a_n) se cere sa se determine al k-lea cel mai mic element cu 1≤k≤n.

Deci, la pasul 1 se determina a_k=min si se interschimba a₁ cu a_k, la pasul 2 se determina a_k=min si se interschimba a₂ cu a_k, la pasul 3 se determina a_k=min si se interschimba a₃ cu a_k, …, la pasul i se determina a_k=min si se interschimba ai cu a_k, …, pana la pasul n-1 se determina a_k=min si se interschimba a_n-1 cu a_k.

Procedura pentru sortarea prin selectie este SortSel_C:

procedure SortSel_C(var A:vector; n:integer);

var x,i,j,k:integer;

begin

for i:=1 to n-1 do

begin

k:=i;

x:=A[i];

for j:=i+1 to n do

if A[j]<x then

begin

k:=j;

x:=A[k];

end;

A[k]:=A[i];

A[i]:=x;

end;

end;

2.1.5 Metoda bulelor(Bubble sort).

Algoritmul de interschimbare consta in modificari succesive de forma a_i↔a_j (interschimbarea lui a_i cu a_j) pana cand elementele vectorului apar in ordinea ceruta de utilizator(crescatoare, in exemplul nostru). Din categoria algoritmilor de interschimbare fac parte metoda bulelor(Bubble sort) care va fi descrisa in acest paragraf, si metoda interschimbarii directe(care va fi discutata in paragraful urmator).

Metoda bulelor se mai numeste si sortarea prin interschimbare cu „fanion”.

Vom introduce notatia a_i<>a_j care presupune ca se compara a_i cu a_j si (numai daca a_i>a_j ) se efectueaza interschimbarea a_i↔a_j.

Metoda are n-1 etape. In prima etapa se efectueaza operatiile: a₁<>a₂; a₂<>a₃; a_n-1<>a_n. In urma acestor operatii a₁ se va deplasa spre dreapta(se va „ridica”) peste toate elementele mai mici decat el pana la primul a_i mai mare decat el. In continuare acelasi lucru se va intampla si cu a_i etc. In concluzie cel mai mare element va fi plasat pe ultima pozitie. Evident in etapa k se vor efectua operatiile: a₁<>a₂ ; a₂<>a₃; a_n-k <>a_n-k+1.

Procedura care implementeaza algoritmul este SortBubble_C:

procedure SortBubble_C(var A:vector; n:integer);

var x,i:integer;

ok:boolean;

begin

repeat

ok:=true;

for i:=1 to n-1 do

if A[i]>A[i+1] then

begin

x:=A[i];

A[i]:=A[i+1];

A[i+1]:=x;

ok:=false;

end;

until (ok=true);

end;

2.1.6.Sortare prin interschimbare directa.

Metoda interschimbarii directe este asemanatoare cu cea anterioara diferentele evidentiindu-se la modul de comparare. In prima etapa se efectueaza operatiile: a₁<>a₂; a₁<>a₃; a₁<>a_n, etc., in etapa k se vor efectua operatiile a_k<>a_k+1; a_k<>a_k+2; a_k<>a_n iar in ultima etapa se va efectua operatia a_n-1<>a_n.

Procedura SortIntersch_C realizeaza algoritmul descris:

procedure SortIntersch_C(var A:vector; n:integer);

var x,i,j:integer;

begin

for i:=1 to n-1 do

begin

for j:=i+1 to n do

if A[i]>A[j] then

begin

x:=A[i];

A[i]:=A[j];

A[j]:=x;

end;

end;

end;

3. Meniul aplicatiei

Aplicatia Sortari.exe foloseste un meniu pentru interactiunea cu utilizatorul, pentru introducerea elementelor vectorului de sortat, alegerea metodei de sortare si ordinea(crescatoare, descrescatoare) in care vor fi sortate elementele.

1. Primul ecran se prezinta astfel:

2. Dupa introducerea numarului de elemente ale vectorului notat A, se trece la introducerea fiecarui element in parte:

3. Meniul principal ofera apoi, utilizatorului, optiuni in privinta metodei de sortare a vectorului:

4. In continuare, dupa alegerea metodei, utilizatorul este rugat sa specifice modul de ordonare a elementelor vectorului:

5. In final vectorul este afisat ordonat, in functie de optiune: