Categoria: lectii

Interclasarea a doi vectori

Postat de: Webmateinfo | Data: 2010-03-09

Avand la dispozitie două tablouri unidimensionale (doi vectori) care au elementele ordonate crescător (sau descrescător) ne punem problema construirii unui al treilea tablou care să contină elementele primelor două respectând acelasi criteriu de ordonare (crescător sau descrescător).
O primă idee ar fi aceea de a reuni elementele celor doi vectori, retinem rezultatul în cel de al treilea si apoi îl sortăm pe acesta crescător sau descrescător, în functie de cum erau ordonati vectorii initiali.
1. pornim cu vectorul C gol (k=0) si primele elemente din A si din B (i=1, j=1)
2. cât timp avem elemente în ambii vectori (i<=n si j<=m)
a. comparăm elementul Ai cu elementul Bj
b. incrementăm k
c. adăugăm la C, pe pozitia k, elementul mai mic dintre Ai si Bj
d. incrementăm indicele corespunzător vectorului din care am făcut adăugarea (incrementăm i dacă
elementul Ai a fost mai mic si în caz contrar j)
3. verificăm în care dintre cei doi vectori au mai rămas elemente
a. dacă i<=n atunci înseamnă că mai avem elemente în vectorul A pe care le luăm în ordine si le
adăugăm la C
b. dacă j<=m atunci înseamnă că mai avem elemente în vectorul B pe care le luăm în ordine si le
adăugăm la C
4. algoritmul se încheie, vectorul C contine elementele din A si din B ordonate crescător. C are în total n+m elemente.
Aceasta este doar o scurta descriere, pentru a putea vedea intreg continutul trebuie sa fiti logat!