Divide et Impera

Divide et impera – sortari

Prezentare generala

Divide et impera este o tehnica speciala prin care se pot rezolva anumite probleme. Ideea de baza este aceea de a descompune problema în doua sau mai multe subprobleme similare, dar mai simple, care se rezolva, iar solutiile lor se combina pentru a da rezultatul final. Se presupune ca subproblemele considerate se descompun la rândul lor în mod similar în subprobleme, pâna când se ajunge la probleme ale caror solutii sunt evidente.

Tehnica divide et impera se bazeaza pe ideea de recursivitate: la un anumit moment dat (nivel) avem doua posibilitati:

(1) subproblema curenta are o rezolvare imediata, caz în care recursia se opreste si revin la subproblema anterioara

(2) nu am ajuns la o rezolvare imediata si deci descompun subproblema curenta în 2 sau mai multe subprobleme similare si reiau procedeul pentru fiecare dintre acestea.

Sortarea prin interclasare

Interclasare a doi vectori

Problema interclasarii este urmatoarea: avem doi vectori de numere reale v1 si v2 sortati crescator. Se doreste obtinerea unui al trei-lea vector v3, format din elementele vectorilor v1 si v2 de asemenea sortat crescator.

Rezolvare: consider vectorii v1 de dimensiune m si v2 de dimensiune n, sortati crescator. Definesc vectorul v3 de dimensiune m+n.

Ideea este urmatoarea: compar mereu elementul curent din v1 cu elementul curent din v2.

Pentru aceasta utilizez un indice i, care parcurge vectorul v1 si un indice j care parcurge vectorul v2. Pentru parcurgerea vectorului v3 se foloseste indicele k. Initial toti indicii sunt 0.

La fiecare moment compar v1[i] cu v2[j]. Daca v1[i] < v2[j] atunci v3[k] = v1[i] si cresc indicii i si k cu o unitate (trec la urmatoarele pozitii din vectorii v1 si v3), altfel v3[k] = v2[j] li cresc indicii j si k cu o unitate. Aceste comparatii se efectueaza atâtat rimp cât nu s-a ajuns la capatul nici unuia dintre vectorii v1 si v2.

Daca la un moment dat obtin i=m sau j=n comparatiile se opresc, doarece unul dintre vectori a fost deja complet introdus în vectorul v3. Ramâne doar sa plasam în v3 elementele ramase din celalalt vector, în ordinea în care se afla.

Algoritm:

pornesc cu i=0, j=0, k=0.

atâta timp cât (i<m si j<n) compar v1[i] cu v2[j]

{

daca (v1[i] < v2[j]) atunci v3[k] = v1[i] si i=i+1

altfel v3[k] = v2[j] si j=j+1

cresc inidicele k: k=k+1

}

daca (i<m) //înseamna ca am iesit din ciclare cu j = n

atâta timp cât (i<m) v3[k] = v1[i] si i=i+1, k=k+1

daca (j<n) //înseamna ca am iesit din ciclare cu i = m

atâta timp cât (j<n) v3[k] = v2[j] si j=j+1, k=k+1

afiseaza v3

În acest moment vectorul v3 contine toate elementele din v1 si v2, sortate în ordine crescatoare.

Sortarea prin interclasare

Avem un vector v si dorim sa ordonam elementele sale în ordine crescatoare.

Idee: împart vectorul în doi vectori, pe care îi sortez si apoi îi interclasez. Conform tehnicii divide et impera, fiecare subvector este la rândul sau împartit în alti doi subvectori ce vor fi sortati si apoi interclasati.

Împartirea în subvectori se face pâna când se ajunge la subvectori cu cel mult doua elemente. În acest caz sortarea se reduce la compararea celor doua elemente(eventual am doar un element).

Algoritm

Utilizez doua functii:

- functia intercalsare:

void interclas(int start, int stop, int lim, int v[20])

Aceasta functie considera subvectorii lui v de la poz start la poz lim

de la poz lim+1 la poz stop

si îi interclaseaza.

- functia divimp: void divimp(int start, int stop, int v[20])

Aceasta functie face urmatorul lucru:

- testeaza daca subvectorul lui v aflat între pozitiile start si stop are cel mult doua elemente. În acest caz sortez direct prin comparatia capetelor.

- daca subvectorul are mai mult de doua elemente atunci consider lim=(start+stop)/2 si apelez recursiv functia divimp(start, lim, v), divimp(lim+1, stop, v) dupa care interclasez cu interclasare(start, stop, lim, v).

Descriere a algoritmilor divide et impera.