ALGORITMI DE SORTARE - prin insertie, interschimbare, QuickSort, HeapSort, prin interclasare

Algoritmi de sortare

Algoritmii de sortare permit ordonarea valorilor unui vector crescator sau descrescator. In cele ce urmeaza vom prezenta cativa algoritmi de sortare foarte cunoscuti.

Sortarea prin selectie

Pseudocod

Algoritmul de sortare prin selectie functioneaza dupa urmatorii pasi :

Pentru fiecare i, i=1,2,.,n-1 executa

efectueaza atribuirea l=i 

calculeaza in variabila min, minimul elementelor x[j], j=i+1,i+2,..,n si atribuie valoarea pozitiei pe care se afla minimul, variabilei l 

comuta valorile x[i] si x[l] 

Implementare in limbajul C

# include 'stdio.h'

# include 'conio.h'

int x[20],n,i;

void SortSelect(int x[],int n)

x[l]=x[i] ;

x[i]=min ;

}

void main(void)

printf('nvector initial: ');

for (i=1;i<=n;i++)

printf('%d ',x[i]);

SortSelect(x,n);

printf('nvector sortat: ');

for (i=1;i<=n;i++)

printf('%d ',x[i]);

getch();

Sortari prin insertie

Algoritmii de sortare prin insertie se bazeaza pe urmatoarea idee : considerand ca primele i-1 elemente ale unui vector x sunt sortate, se va insera elementul x[i] intre aceste elemente, astfel incat primele i elemente ale sirului x sa fie ordonate crescator. Operatia se repeta pentru i=1,2,.,n. In situatia in care, pentru stabilirea pozitiei de insertie se utilizeaza un algoritm de cautare secventiala intr-un tabel ordonat, se obtine algoritmul de insertie directa ; daca se utilizeaza algoritmul se cautare binara se obtine algoritmul de insertie binara.

Sortarea prin insertie directa

Pseudocod

Pentru fiecare i, i=2,3,.,n executa

• efectueaza atribuirile aux=x[i] si j=i
• cata vreme x[j-1]>aux deplaseaza-te spre stanga cu o pozitie si efectueaza atribuirea x[j]=x[j-1]
• cand  s-a gasit un element mai mic decat aux (x[j-1]< aux) sau s-a depasit inceputul sirului (j<1) procesul de cautare si insertie s-a terminat si se poate face insertia x[j]=aux

Implementare in limbajul C

# include 'stdio.h'

# include 'conio.h'

int x[20],n,i;

void SortIns(int x[],int n)

x[j]=aux;

}

void main(void)

printf('nvector initial: ');

for (i=1;i<=n;i++)

printf('%d ',x[i]);

SortIns(x,n);

printf('nvector sortat: ');

for (i=1;i<=n;i++)

printf('%d ',x[i]);

getch();

Sortare prin insertie binara

Pseudocod

Pentru fiecare i, i=2,3,.,n executa

efectueaza atribuirile aux=x[i], inc=1, sf=i-1

cat timp inc<=sf executa

gaseste pozitia med=(inc+sf)/2care marcheaza mijlocul subvectorului cu elementele x[inc], x[inc+1],., x[sf]

daca x[med]>aux atunci cautarea se continua in zona cuprinsa intre pozitia inc si med-1, in caz contrar cautarea se continua in zona cuprinsa intre med+1 si sf

fa loc pentru insertia elementului x[i]=aux, deplasand cu o pozitie spre dreapta elementele cuprinse intre pozitia de insertie inc si pozitia i-1

efectueaza insertia x[inc]=aux

Implementare in limbajul C

# include 'stdio.h'

# include 'conio.h'

int x[20],n,i;

void SortInsBin(int n)

for (j=i;j>=inc+1;j--)

x[j]=x[j-1];

x[inc]=aux;

}

void main(void)

printf('nvector initial: ');

for (i=1;i<=n;i++)

printf('%d ',x[i]);

SortInsBin(n);

printf('nvector sortat: ');

for (i=1;i<=n;i++)

printf('%d ',x[i]);

getch();

Sortare prin interschimbare de chei (BubbleSort)

Ideea metodei se bazeaza pe urmatorul rezultat: daca in subvectorul x[1], x[2],.x[ld] comparam succesiv pentru i=1,2,.,ld-1 elementele vecine x[i] si x[i+1] si le comutam daca x[i]>x[i+1] in final, elementul maxim din subvector se va afla pe pozitia ld. Aplicand succesiv aceasta idee pentru ld=n-1, n-2,., 1 se obtine sirul ordonat crescator.

Pseudocod

Executa atribuirea ld=n-1

cat timp ld>=2 execua

pentru fiecare i=1,2,.,ld compara elementele x[i] si x[i+1] ; daca x[i]> x[i+1] atunci comuta x[i] cu x[i+1]

efectueaza atribuirea ld=ld-1

Implementare in limbajul C

# include 'stdio.h'

# include 'conio.h'

int x[20],n,i;

void BubbleSort(int x[],int n)

ld--;

}

while (ld!=1);

void main(void)

printf('nvector initial: ');

for (i=1;i<=n;i++)

printf('%d ',x[i]);

BubbleSort(x,n);

printf('nvector sortat: ');

for (i=1;i<=n;i++)

printf('%d ',x[i]);

getch();

Sortarea rapida (QuickSort

Algoritmul de sortare rapida are la baza metoda divide et impera : problema initiala

- sortarea vectorului de dimensiune n - este descompusa recursiv in doua subprobleme, acestea sunt descompuse la randul lor, de asemenea in doua subprobleme si asa mai departe pana cand subproblemele obtinute se pot rezolva elementar. Problema de sortare a unui vector se poate rezolva elementar daca dimensiunea vectorului este cel mult doi. Ingeniozitatea acestei metode consta in modul in care se gaseste punctul k in care subvectorul curent x[s], x[s+1],., x[d] este portionat in doua. Dupa un numar de pasi valoarea elementului x[s] este memorata in pozitia k astfel incat x[i]<=x[k] pentru s<=i<=k-1 si x[j]>=x[k] pentru k+1<=j<=d.

Determinarea pozitiei k se face dupa un procedeu numit «  arderea la ambele capete ale unei lumanari « : elementul x[s] este comparat succesiv cu elementele x[d], x[d-1] etc. pana cand se intalneste un element x[i] astfel incat x[s]>x[i]( « lumanarea » a fost « arsa » la capatul din dreapta).

Se comuta elementele x[i] si x[s] si elementul x[i] se compara in continuare cu elementele x[s], x[s+1] etc.( se « arde lumanarea » din partea stanga) pana cand se intalneste un element x[j] astfel incat x[j]>x[i]. Procesul continua pana cand elementul x[s] este adus pe pozitia k astfel incat x[i]<=x[k] pentru s<=i<=k-1 si x[j]>=x[k] pentru k+1<=j<=d. Se observa ca pozitia k reprezinta pozitia pe care o va ocupa elementul x[s] in vectorul sortat.

Pseudocod

Se construiesc doua functii : functia Pozitie() si functia Quicksort().

Functia Pozitie() returneaza pozitia k de divizare a vectorului x[s], x[s+1],., x[d] dupa procedeul expus mai sus.

Functia Quicksort() se autoapeleaza recursiv cat timp subvectorii rezultati sunt de dimensiune mai mare ca doi (s<d), producand subvectorii x[s],x[s+1],., x[k-1] si respectiv x[k+1], x[k+2], ., x[d]

Implementare in limbajul C

# include 'stdio.h'

# include 'conio.h'

int x[20],n,i;

int Pozitie(int s,int d)

i=i1+i;

j=j1+j;

}

return i;

void QuickSort(int s,int d)

void main(void)

printf('nvector initial: ');

for (i=1;i<=n;i++)

printf('%d ',x[i]);

QuickSort(1,n);

printf('nvector sortat: ');

for (i=1;i<=n;i++)

printf('%d ',x[i]);

getch();

HeapSort

Algoritmul de sortare prin selectie se bazeaza pe doua notiuni importante: notiunea de arbore de selectie si de movila(heap). Legatura dintre cele doua notiuni este urmatoarea : prin parcurgerea in latime a unui arbore de selectie se obtine o movila.

Prin definitie un arbore de selectie este un arbore binar care indeplineste urmatoarele conditii :

este binar de inaltime minima

toate nivelele (exceptie facand eventual ultimul) sunt complete ; completarea ultimului nivel se face de la stanga la dreapta

cheile pentru orice relatie tata-fiu respecta relatia prestabilita

De exemplu, se poate constata usor ca arborele prezentat mai jos este un arbore de selectie, relatia prestabilita fiind: valoarea nodului tata <= valoarea nodului fiu.

Parcurgerea in latime a acestui arbore va produce vectorul :

Un vector x[n] este movila(heap) daca pentru orice 1<=k<=n/2 sunt satisfacute conditiile : x[k]<=x[2*k] si x[k]<x[2*k+1].

Se observa ca vectorul rezultat prin parcurgerea in latime a arborelui de selectie prezentat mai sus este o movila. De asemenea , se poate constata usor ca, intr-un heap, elementul situat pe prima pozitie are valoarea minima. Cu alte cuvinte, daca reusim sa transformam un vector intr-un heap, am obtinut implicit, pe prima pozitie si valoarea minima a vectorului. Procedeul poate fi aplicat in continuare subvectorului care incepe cu pozitia a doua a vectorului obtinandu-se pe aceasta pozitie al doilea element al vectorului sortat, si asa mai departe, pana cand tot vectorul a fost sortat.

Pseudocod

Se construiesc doua functii : functia Propagare() si functia HeapSort().

Functia Propagare() aduce in radacina a unui subarbore valoarea cea mai mica dintre elementele subarborelui, transformandu-l intr-un arbore de selectie. Imaginea liniarizata, prin parcurgerea in latime a acestui arbore, este un heap.

Functia HeapSort() are doua sectiuni. In prima sectiune se transforma vectorul initial intr-un heap, aplicand succesiv de la frontiera arborelui de selectie corespunzator(i=n/2, n/2-1, n/2-2 ,.,1) spre nodul radacina, functia Propagare(). In cea de-a doua sectiune se realizeaza sortarea propriu-zisa.

Astfel, pentru fiecare i=n,n-1,n-2,.,2 se executa :

comutarea elementelor x[1] si x[i]

apelul functiei Propagare() pentru subvectorul x[1], x[2],., x[i-1]

Implementare in limbajul C

# include 'stdio.h'

# include 'conio.h'

int x[20],n,i;

void Propagare(int x[],int k,int n)

}

else prop=0;

}

x[k]=aux;

void HeapSort(int x[],int n)

void main(void)

printf('nvector initial: ');

for (i=1;i<=n;i++)

printf('%d ',x[i]);

HeapSort(x,n);

printf('nvector sortat: ');

for (i=1;i<=n;i++)

printf('%d ',x[i]);

getch();

Sortare prin interclasare

Sortarea prin interclasare foloseste ideea construirii rapide a unui sir ordonat pornind de la doua siruri deja ordonate. Practic, dandu-se doua siruri ordonate x[n] si y[m], daca i arata valoarea curenta din x[n], iar j valoarea curenta din y[m], atunci sirul z[m+n] se construieste transferand la fiecare pas k, valoarea min(x[i],y[j]) in z[k] . In cazul in care intr-unul din sirurile de intrare elementele se epuizeaza, elementele netransferate in vectorul z din al doilea sir se copiaza in vectorul z, in continuarea celor existente.

In algoritmul de sortare prin interclasare prezentat mai jos, vectorul initial se divide pana cand vectorii rezultati au marimi mai mici sau egale cu doi (metoda divide et impera). Vectorii cu astfel de marimi pot fi sortati cu usurinta. Prin interclasarea pas cu pas a acestora va rezulta in final  vectorul sortat.

Pseudocod

Se folosesc trei functii : functia Sort(), functia Interclas() si functia Divizare() 

Functia Divizare() realizeaza divizarea unui subvector x[p], x[p+1],..x[q] in doua parti egale, pana cand q-p<=1;

Functia Sort() realizeaza sortarea vectorilor de dimensiune mai mica sau egala cu doi

Functia Interclas() realizeaza sortarea vectorului initial, prin interclasarea pas cu pas a subvectorilor sortati

Implementare in limbajul C

# include 'stdio.h'

# include 'conio.h'

int a[20],n,i;

void Sort(int a[],int p,int q)

void Interclas(int a[],int p,int d,int q)

else

k++;

}

if (i<=d)

for (l=i;l<=d;l++)

else

for (l=j;l<=q;l++)

k=1;

for (i=p;i<=q;i++)

void Divizare(int a[],int p,int q)

void main(void)

printf('nvector initial: ');

for (i=1;i<=n;i++)

printf('%d ',a[i]);

Divizare(a,1,n);

printf('nvector sortat: ');

for (i=1;i<=n;i++)

printf('%d ',a[i]);

getch();

Sortare prin numarare

Ideea pe care o exploateaza algoritmul prin numarare este foarte simpla: pozitia unui element intr-un sir sortat este data de numarul elementelor mai mici decat el, la care adunam valoarea 1. Daca in nr[i] vom contoriza numarul elementelor mai mici decat x[i], atunci, dupa ce contorizarea s-a terminat, valoarea nr[i]+1 va arata pozitia elementului x[i] in sirul ordonat. Vectorul ordonat se obtine intr-un nou vector. In programul de mai jos acesta a fost notat cu y.

Implementare in limbajul C

# include 'stdio.h'

# include 'conio.h'

int x[20],y[20],n,i;

void SortNum(int x[],int n)

void main(void)

printf('nvector initial: ');

for (i=1;i<=n;i++)

printf('%d ',x[i]);

SortNum(x,n);

printf('nvector sortat: ');

for (i=1;i<=n;i++)

printf('%d ',y[i]);

getch();