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