Tematică științifică · 1.7

Algoritmul de interclasare

Construirea unui al treilea vector ordonat din doi vectori ordonați, printr-o singură parcurgere — algoritmul cu doi indici, copierea elementelor rămase, ordinul de complexitate și aplicațiile.

Interclasarea este operația prin care, din doi vectori ordonați după același criteriu, se obține un al treilea vector, ordonat după același criteriu, care conține toate elementele celor doi.

Condiția ca vectorii de la intrare să fie ordonați este cea care face operația eficientă: rezultatul se obține dintr-o singură parcurgere a fiecăruia dintre ei.

Algoritmul stă la baza sortării prin interclasare, studiată la metoda divide et impera, dar apare la examen și ca cerință de sine stătătoare.

Descrierea algoritmului

Cei doi vectori se parcurg simultan, cu câte un indice pentru fiecare, pornind de la prima poziție. La fiecare pas se compară elementele aflate pe pozițiile curente și se scrie în rezultat cel mai mic dintre ele. Indicele vectorului din care s-a scris înaintează cu o poziție.

Prelucrarea continuă până când unul dintre vectori se epuizează. Elementele rămase în celălalt sunt mai mari decât toate cele scrise până atunci și sunt ordonate între ele, deci se copiază în rezultat fără a mai fi comparate: nu mai există cu ce să fie comparate.

Pașii algoritmului

Se folosesc trei indici: i pentru vectorul a, j pentru vectorul b și k pentru vectorul rezultat, c.

Pasul	Ce se execută
Pas 1.	Se inițializează indicii: `i ← 1`, `j ← 1` și `k ← 0`.
Pas 2.	Dacă `i ≤ n` și `j ≤ m`, adică mai sunt elemente în amândoi vectorii, se merge la Pas 3; altfel, se merge la Pas 4.
Pas 3.	Dacă `a[i] ≤ b[j]`, se scrie în rezultat elementul din a: `k ← k + 1`, `c[k] ← a[i]`, `i ← i + 1`; altfel, se scrie elementul din b: `k ← k + 1`, `c[k] ← b[j]`, `j ← j + 1`. Se revine la Pas 2.
Pas 4.	Unul dintre vectori s-a epuizat. Cât timp `i ≤ n`, elementele rămase în a se copiază în rezultat: `k ← k + 1`, `c[k] ← a[i]`, `i ← i + 1`.
Pas 5.	Cât timp `j ≤ m`, elementele rămase în b se copiază în rezultat: `k ← k + 1`, `c[k] ← b[j]`, `j ← j + 1`.
Pas 6.	Vectorul c conține cele n + m elemente, în ordine crescătoare. Algoritmul se încheie.

Pașii 4 și 5 se scriu amândoi, deși se execută cel mult unul: din structura de la Pas 2 s-a ieșit fiindcă unul dintre vectori s-a epuizat, deci celălalt este singurul care mai poate avea elemente.

Exemplu. Vectorii a = (1, 4, 7) și b = (2, 3, 8).

Pasul	Se compară	Se scrie	Rezultatul
1	1 și 2	1, din a	1
2	4 și 2	2, din b	1 2
3	4 și 3	3, din b	1 2 3
4	4 și 8	4, din a	1 2 3 4
5	7 și 8	7, din a	1 2 3 4 7
6	vectorul a s-a epuizat	8, elementul rămas în b	1 2 3 4 7 8

Algoritmul în pseudocod

i ← 1; j ← 1; k ← 0
cât timp i ≤ n și j ≤ m execută
    dacă a[i] ≤ b[j] atunci
        k ← k + 1; c[k] ← a[i]; i ← i + 1
    altfel
        k ← k + 1; c[k] ← b[j]; j ← j + 1
    sfdacă
sfcât timp

cât timp i ≤ n execută
    k ← k + 1; c[k] ← a[i]; i ← i + 1
sfcât timp

cât timp j ≤ m execută
    k ← k + 1; c[k] ← b[j]; j ← j + 1
sfcât timp

Materialul acesta se citește pe educamp.ro și nu se tipărește.

Ce cuprinde subcapitolul

Descrierea algoritmului
Algoritmul în pseudocod
Implementarea
Ordinul de complexitate
Aplicații

Continuă lectura ca și cursant

Cel puțin un subcapitol din fiecare capitol este disponibil gratuit și integral. Pentru a citi toate celelalte subcapitole ale disciplinei, te înscrii la cursul de pregătire.

Cursul cuprinde suportul de curs publicat până acum, care se completează capitol cu capitol, și două întâlniri de câte două ore în fiecare lună. Prima săptămână este gratuită, fără plată și fără card. Dacă vrei să vezi mai întâi cum este prezentată materia, poți reveni la primul subcapitol al capitolului.

Începe săptămâna gratuită Sunt cursant — login

Află când publicăm materiale noi

Materia este publicată treptat, capitol cu capitol. Înscrie-te pentru a primi un e-mail atunci când apare un capitol nou de informatică.

Surse

Cerchez, E., Șerban, M., „Programarea în limbajul C/C++ pentru liceu”, Editura Polirom, Iași, 2005
Gheorghe, M. (coord.), Tătărâm, M., Achinca, C., Năstase, C., „Informatică. Manual pentru clasa a XI-a”, Editura Corint, București, 2008
Huțanu, V., Sorin, T., „Informatică. Manual pentru clasa a XI-a”, Editura L&S Soft, București, 2006
„Metode și tehnici clasice de programare”, suport de curs