[C++]Interclasarea a 2 vectori

[~Wolf~]

Algoritm pentru interclasarea a 2 vectori

Revin cu un nou tutorial.Multa inactivitate, da, da, stiu.Apropo, pentru nelamuriri/greseli va rog sa lasati PM sau reply.

Ce inseamna interclasarea a 2 vectori?

In primul rand, ce trebuie sa stiti este ca ambii vectori necesita sa fie obligatoriu ordonati crescator sau descrescator.Acest algoritm sorteaza cei doi vectori in ordine crescatoare sau descrescatoare.

Stiu deja algoritmul de sortare, nu imi trebuie interclasarea ca sa sortez 2 vectori

Big NO, in cazul in care vi se cere eficienta.Vedeti voi, sortarea se face in O(n^2), pe cand interclasarea in O(n), fiind foarte vizibila eficienta sa.

*insa de ce nu, daca nu vi se cere eficienta puteti face sortare

Interclasarea a 2 vectori -> Ordine crescatoare

#include <fstream>
using namespace std;

//OBSERVATIE!
//cand avem si fisier de intrare dar si fisier de iesire putem include
//doar libraria fstream, nefiind necesara si iostream(dar se poate pune si asta,
//nu vi se vor afisa erori)

ifstream fin("interclasare.in"); //definim 2 fisiere(cel de intrare) ca sa nu scriem toate numerele de fiecare data cand le citim
ofstream fout("interclasare.out");//(cel de iesire)

unsigned int n,m,i,j,k,p;//ne declaram variabilele

int main()
{
fin>>n;//citim primul numar, declaram primul vector si il citim
unsigned int a[n];
for(i=0;i<n;i++)
fin>>a[i];
fin>>m;//citim al doilea numar, declaram al doilea vector si il citim
unsigned int b[m];
for(j=0;j<m;j++)
fin>>b[j];
//luam de la 0 i si j pentru a parcurge vectorii de la inceput
//acel k va fi memoria totala a vectorului final c, pe care de asemenea,
//o incepem de la 0
i=0; j=0; k=0;
unsigned int c[n+m];//vectorul unde vom memora elementele celor doi vectori sortati CRESCATOR
while(i<n && j<m)//incepem interclasarea
{
//in acest "if" si "else" comparam fiecare element cu fiecare din cei 2 vectori
//salvandu-i in ordine crescatoare
if(a[i]<b[j])//o sa fac un exemplu mai jos
{
c[k]=a[i];//memoram elementul din vectorul a, deoarece este mai mic decat cel din b
i++;//ne deplasam la urmatorul element
k++;//crestem dimensiunea vectorului c
}
else
{
c[k]=b[j];//idem ca mai sus
j++;
k++;
}
}
//aici vom verifica pe rand daca mai sunt elemente ramase in vectori
//de mentionat ca toate elementele ramase sunt ORDONATE CRESCATOR OBLIGATORIU
if(i<n)//verificare pentru vectorul a
{
for(p=i;p<n;p++)//memoram elementele ramase din vectorul a in vectorul c
{
c[k]=a[p];
k++;//crestem dimensiunea vectorului c
}
}
if(j<m)//verificare pentru vectorul b
{
for(p=j;p<m;p++)//analog
{
c[k]=b[p];
k++;
}
}
for(p=0;p<k;p++)//iar in final, afisam vectorul
fout<<c[p]<<' ';
return 0;
}

Exemplu:


n=5
a[5]={3, 6, 12, 41, 99}
m=3
b[3]={2, 38, 67}


Se va afisa:


2 3 6 12 38 41 67 99


Explicatie:


Citim numerele si vectorii.Si ajungem aici:
i=0;j=0;k=0;

Incepem cu while(i<n && j<m) <=> while(0<5 && 0<3) "ADEVARAT"
if(a[i]<b[j]) <=>if(a[0]<b[0]) <=> 3<2 "FALS", se trece la else si executam instructiunile:
c[k]=b[j] <=> c[0]=b[0] <=>c[0]=2, j++, adica j=1, k++, adica k=1

if(a[i]<b[j]) <=>if(a[0]<b[1]) <=> 3<38 "ADEVARAT", executam instructiunile if-ului
c[k]=a[i] <=> c[1]=a[0] <=> c[1]=3, i++, adica i=1, k++, adica k=2

if(a[i]<b[j]) <=> if(a[1]<b[1]) <=> 6<38 "ADEVARAT", executam instructiunile if-ului
c[k]=a[i] <=> c[2]=a[1] <=> c[2]=6, i++, adica i=2, k++, adica k=3

Si tot asa, iar la finalul while-ului vom termina de parcurs al 2-lea vector(b),unde j=3, i=4,k=7 si vom avea urmatorii vectori:
a[5]={3, 6, 12, 41, 99}
b[3]={2, 38, 67}
c[7]={2, 3, 6, 12, 38, 41, 67}

Ce facem de acum?Verificam daca mai sunt elemente ramase in vectori.Verificam pentru vectorul a:

if(i<n) <=> 4<5 "ADEVARAT" si intram in for:
for(p=4;4<5("ADEVARAT");p++(adica p=5)), c[k]=a[p] <=> c[7]=a[4] <=> c[7]=99, k++, adica k=8
for(p=5;5<5("FALS");p++) - terminam for-ul

Verificam pentru vectorul b:

if(j<m) <=> 3<3 "FALS"

Iar de acum vom afisa vectorul c[8], unde c[8]={2, 3, 6, 12, 38, 41, 67, 99}