Metode de sortare
1. Metoda bulelor : se comparã perechi de elemente si dacã nu
îndeplinesc conditia de ordonare li se interschimbã valorile, pânã când întreg
vectorul este sortat. Variabila booleanã o are rolul de a opri ciclarea dacã nu
s-a mai efectuat nici o schimbare de elemente în cursul ultimei treceri prin
vector.
var v:array[1..10] of integer;
n,i,x:integer;
o:boolean;
begin write('n='); read(n);
for i:=1 to n do read(v[i]);
repeat
o:=true;
for i:=1 to n-1 do
if v[i]>v[i+1] then begin
x:=v[i]; v[i]:=v[i+1]; v[i+1]:=x;
o:=false;
end;
until o;
for i:=1 to n do write(v[i]:3);
end.
2. Metoda insertiei binare : la fiecare din cei n-1 pasi realizeazã
inserarea elementului i în tabloul ce contine deja i-1 elemente sortate.
Determinarea pozitiei de inserare se face prin cãutare binarã, reducând astfel
numãrul mediu de comparatii necesare pentru determinarea pozitiei de
inserare.
var v:array[1..10] of integer;
n,i,x,s,d,j:integer;
begin write('n='); read(n);
for i:=1 to n do read(v[i]);
for i:=2 to n do begin
x:=v[i]; s:=1; d:=i-1;
while s<=d do begin
j:=(s+d) div 2;
if x<v[j] then d:=j-1
else s:=j+1;
end;
for j:=i-1 downto s do v[j+1]:=v[j];
v[s]:=x;
end;
for i:=1 to n do write(v[i]:3);
end.
3. Sortare prin interschimbare : metoda are n-1 etape. În prima etapã
se comparã v[1] cu v[2], v[2] cu v[3],..., v[n-1] cu v[n] si dacã v[i]>v[i+1] se
efectueazã interschimbarea v[i]v[i+1]. Dupã aceastã etapã cel mai mare
element este plasat pe ultima pozitie în vector. În etapa k se comparã v[1] cu
v[2], v[2] cu v[3], ..., v[n-k] cu v[n-k+1]. Varianta îmbunãtãtitã a acestei
metode este metoda bulelor, la care s-a introdus o variabilã booleanã pentru
sesizarea terminãrii sortãrii înaintea parcurgerii tuturor etapelor.
var v:array[1..10] of integer;
n,i,j,x:integer;
begin write('n='); read(n);
for i:=1 to n do read(v[i]);
for i:=1 to n-1 do
for j:=1 to n-1 do
if v[j]>v[j+1] then begin
x:=v[j]; v[j]:=v[j+1]; v[j+1]:=x;
end;
for i:=1 to n do write(v[i]:3);
end.
4. Sortare prin selectie : se selecteazã repetat elementul cel mai mic
din cele rãmase de sortat la un moment dat si se plaseazã pe pozitia curentã
i.
var v:array[1..10] of integer;
n,min,poz,i,j:integer;
begin write('n='); read(n);
for i:=1 to n do read(v[i]);
for i:=1 to n-1 do begin
poz:=i; min:=v[i];
for j:=i+1 to n do
if v[j]<min then begin min:=v[j]; poz:=j; end;
v[poz]:=v[i]; v[i]:=min;
end;
for i:=1 to n do write(v[i]:3);
end.
5. Sortare prin numãrare : se comparã fiecare valoare v[i] cu toate
celelalte si se numãrã câte valori mai mici decât ea existã. Numerele astfel
obtinute se memoreazã în vectorul contor. Dacã s-au gãsit j valori mai mici
decât v[i], locul lui v[i] va fi pe pozitia j+1 în vectorul sortat. Pe baza
vectorului contor se rearanjeazã elementele din v în vectorul sortat w.
Metoda foloseste spatiu suplimentar de memorie, prin folosirea vectorilor de
lucru contor si w.
var v,contor,w:array[1..10] of integer;
n,i,j:integer;
begin write('n='); read(n);
for i:=1 to n do read(v[i]);
for i:=2 to n do
for j:=1 to i-1 do
if v[i]<v[j] then inc(contor[j])
else inc(contor[i]);
for i:=1 to n do w[contor[i]+1]:=v[i];
for i:=1 to n do write(w[i]:3);
end.
6. Sortare rapida: Foloseste o procedura care aplicata unui sir de
numere, pozitioneaza primul element din sir pe pozitia pe care se va afla
acesta în sirul sortat şi deplaseaza elementele din sir mai mici decât acesta în
stanga, iar pe cele mai mari în dreapta.
Pentru parcurgerea secventei se va folosi indicele i (pt capatul st.) şi
indicele j (pt capatul dr.). La fiecare pas se compara elementele de pe
pozitiile i şi j; daca elem de pe poz. i este mai mare decât cel de pe poz. j, le
interschimbam. Cadn apare o interschimbare se schimba şi modul de
parcugere a vect. Parcurgerea incepe din dreapta. Pentru deplasarea lui i şi j
s-au folosit variabilele di şi dj. La fiecare pas parcurgerea se modifica astfel:
a) la parcurgerea din st.: i creste şi di=1; j ramane neschimbat, dj=0;
b) la parcurgerea din dr.:i ramane neschimbat, di=0; j scade, dj=1
At. când apare o interschimbare a elementelor, modificare sensului de
parcurgere se face interschimband şi valorile di cu dj.
program quick;
type vector=array[1..50] of integer;
var a:vector;
n,i:integer;
function pivot(st,dr:integer):integer;
var aux,i,j,di,dj:integer;
begin
i:=st;j:=dr;
di:=0;dj:=1;
while i<j do
begin
if a[i]>a[j] then begin
aux:=a[i];
a[i]:=a[j];
a[j]:=aux;
aux:=di;
di:=dj;
dj:=aux;
end;
i:=i+di;
j:=j-dj;
end;
pivot:=i;
end;
procedure sort(st,dr:integer);
var p:integer;
begin
if st<dr then begin
p:=pivot(st,dr);
sort(st, p-1);
sort(p+1,dr);
end;
end;
begin
write('n=');readln(n);
for i:=1 to n do
begin
write('a[',i,']=');readln(a[i]);
end;
sort(1,n);
for i:=1 to n do
write(a[i]:4);
readln;
end.
7. Sortare prin interclasare: foloseste DI pentru a imparti sirul de intrare
înmod recursiv până la subsiruri de unul sau doua elemente. Acestea sunt
sortate folosind cel mult o comparatie şi o nterschimbare, apoi sunt
interclasate în secvente din ce în ce mai mari, obtinandu-se în fnal o
secventa de lungimea sirului initial, sortata.
Algoritmul de sortare implica 3 etape:
- sirul este impartit de la jumatate în doua subsiruri de lugimi egale (sau
difera prin cel mult o unitate);
- cele doua siruri sunt sortate recursiv
- subsirurile sortate se interclaseaza.