Algoritm pentru interclasarea a doi vectori

Interclasarea a doi vectori inseamna reuniunea celor doi vectori simultan cu or­donarea elementelor vectorului rezultat.

Presupunem ca cei doi vectori sunt sortati (crescator sau descrescator). Prin acest algoritm se parcurg simultan cei doi vectori sursa pentru a se compara un element dintr-un vector cu un element din celalalt vector.

Elementul cu valoarea mai mica. respectiv mai mare, este copiat in vectorul destinatie si sters din vectorul sursa. Procesul continua pana cand este epuizat unul dintre vectori. Elementele ramase in celalalt vector se adauga la sfarsitul vectorului destinatie.

Se folosesc urmatoarele variabile de memorie pentru:

- vectori: a si b - vectorii sursa (se presupune ca sunt deja sortati crescator sau descrescator) si c - vectorul rezultat (vectorul destinatie) care reuneste elemen­tele din vectorii a si b, ordonate dupa acelasi criteria ca si cele din vectorii sur­sa:

- lungimile logice ale vectorilor: n - pentru vectorul a (se introduce de la tastatura) si m - pentru vectorul b (se introduce de la tastatura); lungimea vectorului c se calculeaza (n+m);

- contorii pentru parcurgerea vectorilor: i - pentru vectorul a, j - pentru vecto­rul b si k - pentru vectorul c.

Pasii algoritmului (pentu vectori sortati crescator) sunt:

Pas 1.          Se initializeaza variabilele contor, pentru vectorii surse si pentru vectorul rezultat, cu 0: i=0; j=0; k=0;.

Pas 2. Se compara elementele a[i] §i b[j]. Daca a[i]<b[j] se copiaza elementul a[i] in vectorul c prin c[k]=a[i] si se sterge elementul a[i] din vectorul a; altfel, se copiaza elementul b[j] in vectorul c prin c[k]=b[j] si se sterge elementul b[j] din vectorul b. Operatia de stergere nu se execute prin eliminarea efecti­va a elementului din vector, ci prin incrementarea contorului: dace se ster­ge elementul din vectorul a se incrementeaza contorul i (i=i+1), iar dace se sterge elementul din vectorul b se incrementeaza contorul j (j=j+1).

Pas 3. Se incrementeaza contorul k pentru ca urmeaza sa se copieze un element in acest vector.

Pas 4.       Se compara contorii vectorilor sursa cu lungimea lor. Daca fiecare contor este mai mic sau egal cu lungimea vectorului (i<n si j<m) se revive la Pas 2; altfel, se trece la pasul urmator.

Pas 5.          Se adauga la sfarsitul vectorului c elementele ramase in celalalt, printr-o simpla operatie de copiere: daca i<n inseamna ca s-a epuizat vectorul

b si se vor adauga la vectorul c elementele ramase in vectorul a (se exe­cute c[k]=a[i]; k=k+1; i=i+1; pana cand i devine egal cu lungimea n a vectorului a); altfel, s-a epuizat vectorul a si se vor adauga la vectorul c elementele ramase in vectorul b (se execute c[k]=b[j]; k=k+1; j=j+1; pana cand j devine egal cu lungimea m a vectorului b).

Secventa de instructiuni pentru interclasarea a doi vectori sortati crescator este

{int i,j,k,n,m,a[50],b[50],c(100];

cout<< "n =" ; cin>>n; cout<<"m =" ; cin>>m;

for (i=0; i<n; i++)  {cout<<"a["<<i+l<<"]=" ; cin>>a[i]; }

for (j=0; j<m; j++) {cout<<"b["<<j+1<<"]="; cin>>b[j] ; }

i=0; j=0; k=0;

while.(i<n && j<m)

        { if (a:[i]<b[j]) {c[k]=a[i];  i++;}

                            else {c[k]=b[j]; j++;}

          k++; }

if (i<n)

while (i<n) {c [k]=a[i];  k++;  i++; }

     else

while (j<m) {c[k]=b[j]; k++; j++; }

for (k=0; k<n+m; k++) cout<<e[k] <<"    "  };