C++: Interclasarea

Avand la dispozitie doua tablouri unidimensionale, adica 2 vectori, cu elemente ordonate (crescator sau descrescator) trebuie sa construim un al 3-lea tablou care sa contina elementele primelor 2, respectand acelasi criteriu de ordonare.

Varianta I, cu un timp de executie ridicat

O prima idee ar fi aceea de a reuni elementele celor 2 vectori intr-un al 3-lea, pe care sa il sortam apoi crescator sau descrescator. Rezultatul obtinut dupa efectuarea acestei metode este, bineinteles, cel asteptat, insa dupa cum stim operatia de sortare este mare consumatoare de timp si de aceea aceasta metoda este ineficienta, avand in vedere faptul ca beneficiem de vectorii A si B gata ordonati.


Algoritmul cel mai rapid pentru problema data se numeste INTERCLASARE si este foarte cunoscut si important, dar nu pentru incepatori (primul an de studiu). Mai jos, dupa urmarirea unei analize pas cu pas (cu imagini si explicatiile aferente acestora) a unui exemplu concret de interclasare pe vectori, pentru a intelege ideea de la baza interclasarii, veti gasi algorimul ce realizeaza procedeul descris.

Incepem interclasarea, cea mai rapida metoda

• Variabila "i" retine indicele componentei din A care va fi comparata la pasul urmator.
• Variabila "j" retine indicele componentei din B care va fi comparata la pasul urmator.
• Variabila "k" retine indicele componentei din C care va memora urmatorul numar.
• Initial se compara primele elemente din cei 2 vectori, deci i=1 si j=1.
• Primul element in C va fi adaugat pe pozitia 1, deci initial k=1.
• La fiecare pas:

               - comparam elementul de indice "i" din A cu elementul de indice "j" din B si il alegem pe cel mai mic pentru a fi adaugat la vectorul C, pe pozitia "k"
               - dupa fiecare adaugare "k" creste cu 1 si tot cu 1 creste si indicele corespunzator vectorului din care am ales elementul (daca am adaugat la C elementul din A, atunci creste "i", iar daca am adaugat elementul din B, creste "j")

• Acesti pasi ii repetam atata timp cat mai avem elemente neadaugate in ambii vectori (i<=n si j<=m), deci cat timp se justifica compararea valorilor.

Se continua interclasarea

• Dupa efectuarea operatiilor din prima figura continuam executarea lor dupa aceleasi reguli si in figura a doua.
• Ne oprim cu aceste operatii in momentul in care am adaugat deja toate elementele unui vector, in cazul nostru A, insa interclasarea nu se termina aici, pentru ca au ramas elemente neadaugate din celalalt vector (adica, pe caz, B).
• Profitand de faptul ca vectorul este ordonat crescator nu trebuie decat sa copiem elementele ramase in vectorul C. Pe exemplu nostru, in vectorul B a ramas un singur element (anume 8), dar acest lucru nu este general valabil, dupa 8 putand avea si alte elemente si atunci toate ar fi trebuit adaugate vectorului C.
• Dupa cum am observat nu au ramas elemente in vectorul care avea mai multe, ci in cel cu mai putine (n>m), deci nu numarul de elemente este cel care ne spune in care vector vor ramane valori. Acest lucru depinde strict de valorile elementelor din vectori.

Astfel, algortimul de interclasare este:
           k=0; i=1; j=1;
           while(i<=n && j<=m)
                      if(a[i]<b[j])
                      {
                               k++;
                               c[k]=a[i];
                               i++;
                      }
                      else
                      {
                               k++;
                               c[k]=b[j];
                               j++;
                      }
           if(i<=n)
                      for(l=i; l<=n; l++)
                      {
                              k++;
                              c[k]=a[l];
                       }

          else

                      for(l=j; l<=m; l++)

                      {

                              k++;

                              c[k]=b[l];

                       }