Sorozatok összefésülése

Értelmezés: összefésülés == két rendezett sorozatból gyártunk egy harmadik rendezett sorozatot, mely tartalmazza a két sorozat minden elemét.

Fésüljünk össze két növekvő sorozatot szintén növekvő sorrendbe!

Pl.
    bemenet:
        1 3 5           2 3 4
    kimenet:
        1 2 3 3 4 5

Ötlet: két indexszel egyszerre végigjárjuk a sorozatokat

     1 3 5           2 3 4
          ^               ^
          i               j

    eredmény:
        1 2 3 3 4 5

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <iostream>
using namespace std;

int main()
{
    int n1;
    cin >> n1;
    int t1[1000];
    for(int i = 0; i < n1; i++){
        cin >> t1[i];
    }

    int n2;
    cin >> n2;
    int t2[1000];
    for(int i = 0; i < n2; i++){
        cin >> t2[i];
    }

    int eredmeny[2000];
    int c = 0; // hol tartok az eredmeny-ben?
               // == hány elemet tettem eddig bele?

    int i1 = 0;
    int i2 = 0;

    while (i1 < n1 && i2 < n2) {
            // amíg egyik tömb sem fogyott el

        if (t1[i1] <= t2[i2]) {
            eredmeny[c] = t1[i1];
            i1++;
            c++;
        }
        else {
            eredmeny[c] = t2[i2];
            i2++;
            c++;
        }
    }

    // még át kell másolni a maradékot
    // (t1-ből v. t2-ből eredmeny-be)
    while (i1 < n1) {
        eredmeny[c] = t1[i1];
        i1++;
        c++;
    }

    while (i2 < n2) {
        eredmeny[c] = t2[i2];
        i2++;
        c++;
    }

    // kiírás
    for (int i = 0; i < c; i++)
        cout << eredmeny[i] << " ";
    
    cout << endl;
    return 0;
}

Feladatok

1. (HF) Összefésülés két csökkenő sorozatból csökkenő sorrendbe

Megoldás: csak az if-beli <= jelet kell >= jelre cserélni.

2. (HF) Adott két sorozat, az első növekvő, a második csökkenő. Fésüljük össze az elemeiket növekvő sorrendbe!

    Pl.
        3               4
        1 3 5           4 3 2 1
        ^                     ^

    kimenet:
        1 1 2 3 3 4 5

Megoldás: ld. az alábbi feladat megoldását (minimális módosítással)

3. (HF) Adott két sorozat, az első csökkenő, a második növekvő. Fésüljük össze az elemeiket csökkenő sorrendbe!

    Pl.
        4               3
        4 3 2 1         1 3 5
        ^                   ^

    kimenet:
        5 4 3 3 2 1 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <iostream>
using namespace std;

int main()
{
    int n1;
    cin >> n1;
    int t1[1000];
    for(int i = 0; i < n1; i++){
        cin >> t1[i];
    }

    int n2;
    cin >> n2;
    int t2[1000];
    for(int i = 0; i < n2; i++){
        cin >> t2[i];
    }

    int eredmeny[2000];
    int c = 0; // hol tartok az eredmeny-ben?
               // == hány elemet tettem eddig bele?

    int i1 = 0;
    int i2 = n2 - 1;

    while (i1 < n1 && i2 >= 0){
        if (t2[i2] <= t1[i1]){
            eredmeny [c] = t1 [i1];
            i1++;
            c++;
        }
        else {
            eredmeny [c] = t2 [i2];
            i2--;
            c++;
        }
    }

    while (i1 < n1) {
        eredmeny [c] = t1 [i1];
        i1++;
        c++;
    }

    while (i2 >= 0) {
        eredmeny [c] = t2 [i2];
        i2--;
        c++;
    }

    // kiírás
    for (int i = 0; i < c; i++)
        cout << eredmeny[i] << " ";

    cout << endl;
    return 0;
}