Download - (290182205) PA_3
Proiectarea algoritmilor
Proiectarea algoritmilor
Scheme de algoritmi
1
2
DIVIDE ET IMPERA
3
DIVIDE ET IMPERA
4
Divide et imperaAvantaje i dezavantajeDivide et impera- Algoritmi simplide sortare a tablourilor
Sortarea tabloului este ordonarea compo-nentelor acestuia dup valoarea lor.
Dac tipul componentelor tabloului este nume- ric, relaia de ordine este cea specific mulimii de valori a tipului respectiv.
Pentru diferite clase de obiecte se pot, de asemenea, defini relaii de ordine, depinznd de scopul n care se face sortarea.Sortarea prin selecie
Una din cele mai intuitive metode de ordonare a datelor ntr-un tablou este urmtoarea:
Se caut n tablou cel mai mic element i seschimb cu cel de pe prima poziie.
Se caut apoi cel mai mic element dintre cele rmase i se aduce n tablou pe poziia a doua i aa mai departe.n pseudocod, acest algoritm sepoate formula astfel:
Fie tabloul tab cu n componente;
Fie i, j, k numere ntregi;
For i de la 0 la n-2{/* se caut cel mai mic element de pe poziiile i .. n-1 */
k=i; /* s-a notat cu k indicele celui mai mic element */For j de la i la n-1Dac tab[j]>tab[k]Atunci k=j;/* se aduce pe poziia i cel mai mic element de pe poziiile i.. n-1acesta fiind tab[k] */Dac k este diferit de iAtunci se interschimb tab[i] cu tab[k];}Complexitatea acestui algoritm desortare poate fi evaluat astfel:
Pentru fiecare valoare a lui i se fac n-i-1 comparaii, iar i ia valori de la 0 la n-2, deci ordinul de mrime al numrului de operaii elementare este
(n-1)+(n-2)+(n-3)+...+1=[(n-1)+1]*(n-1)/2.
Aceasta nseamn c complexitatea algoritmului de sortare prin selecie este O(n2).Sortarea prin inserie
Se consider c, pentru o poziie oarecare de indice i, zona de tablou de la indicele 0 la i-1 este deja ordonat.
Se ia elementul de pe poziia de indice i i se caut la stnga lui, de la dreapta la stnga, poziia pe care trebuie plasat, a. s se respecte ordinea impus. Fie aceasta poziia de indice jsup) return -1; // interval gresitint k=(inf+sup)/2; // se ia indicele de la mijlocul zonei if(val==tab[k]) return k; // s-a gasit elementul cautat if(val