Tablouri unidimensionale / Interclasarea tablourilor


Editat de Candale Silviu (silviu) la data 2017-12-23
Etichete: nicio etichetă

Considerăm două tablouri unidimensionale cu elemente numere întregi ordonate crescător. Se dorește construirea unui alt tablou, care să conțină valorile din cele două tablouri, în ordine.

O soluție foarte eficientă este interclasarea:

  • considerăm două tablouri, cu n, respectiv m elemente, ordonate crescător
  • cele două tablouri se parcurg concomitent;
  • se alege valoarea mai mică dintre cele două elemente curente
    • se adaugă în al treilea tablou
    • se avansează numai în tabloul din care am ales valoarea de adăugat
  • parcurgerea unuia dintre cele două tablouri se încheie
  • toate elementele din celălalt tablou, neparcurse încă, sunt adăugate în tabloul destinație
  • tabloul destinație are p = n + m elemente

Secvență C++:

int n,a[100000], m , b[100000], p, c[200000];

//citire a[] cu n elemente
//citire b[] cu m elemente

int i = 0 , j = 0;
p = 0;
while(i < n && j < m)
    if(a[i] < b[j])
        c[p ++] = a[i ++];
    else
        c[p ++] = b[j ++];
while(i < n)
    c[p ++] = a[i ++];
while(j < m)
    c[p ++] = b[j ++];

Observație: Doar una dintre instrucțiunile while(i < n)... și while(j < m)... se va executa, deoarece exact una dintre condițiile i < n și j < m este adevărată. În prima structură repetitivă, la fiecare pas, doar una dintre variabilele i și j se mărește, deci la final una dintre condiții este adevărată și una este falsă.

Algoritmul de interclasare este foarte eficient. El are complexitate O(n+m). De asemenea, este posibilă și interclasarea valorilor din două fișiere, singura condiție este ca valorile să fie ordonate.

Fișiere atașate


Probleme ataşate

Nr. Problema Clasa Dificultate Operații I/O
1 #0241 - Interclasare 9 ușoară fișiere
2 #0250 - Interclasare1 9 medie fișiere
3 #0251 - Interclasare2 9 medie fișiere
4 #0284 - Interclasare3 9 medie fișiere
5 #0530 - Multimi1 9 medie consola
6 #0242 - InterclasM 9 medie fișiere

Vezi și: