Sorozatok összefésülése

Az összefésülés (merging) az a művelet, melynek során két rendezett sorozatból egy harmadikat készítünk, mely a két sorozatnak minden elemét tartalmazza.

Példa: két növekvő sorozat összefésülése növekvő sorrendbe.

    5
    1 3 5 60 60
      ^

    6
    2 3 4 5 5 70
        ^

    az eredmény:
       11
       1 2 3 3 4 5 5 5 60 60 70

Példa: két növekvő sorozat összefésülése csökkenő sorrendbe.

    5
    1 3 5 60 60
             ^

    6
    2 3 4 5 5 70
              ^

    eredmény:
        11
        70 60 60 5 5 5 4 3 3 2 1

Implementáció:

Két növekvő sorozatot növekvő sorrendbe fésülünk össze:

 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
#include <iostream>
#include <fstream>
using namespace std;

int main()
{
    int n1, n2;
    int t1[100], t2[100];

    ifstream bemenet("input.txt");

    bemenet >> n1;
    for (int i = 0; i < n1; i++)
        bemenet >> t1[i];


    bemenet >> n2;
    for (int i = 0; i < n2; i++)
        bemenet >> t2[i];

    // összefésülés:
    int t3[200];
    int n3 = 0;

    int i1 = 0; // inde az első tömbbe
    int i2 = 0;

    while (i1 < n1 && i2 < n2) {
        // amíg egyik sem fogyott még el

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

    while (i1 < n1) {
       t3[n3] = t1[i1];
       i1++;
       n3++;
    }

    while (i2 < n2) {
       t3[n3] = t2[i2];
       i2++;
       n3++;
    }

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

Változat:

Tegyük fel, hogy az első sorozat növekvő, a második csökkenő és csökkenő sorrendbe akarunk összefésülni.

 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
#include <iostream>
#include <fstream>
using namespace std;

int main()
{
    int n1, n2;
    int t1[100], t2[100];

    ifstream bemenet("input.txt");

    bemenet >> n1;
    for (int i = 0; i < n1; i++)
        bemenet >> t1[i];


    bemenet >> n2;
    for (int i = 0; i < n2; i++)
        bemenet >> t2[i];

    // összefésülés:
    int t3[200];
    int n3 = 0;

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

    while (i1 >= 0 && i2 < n2) {
        // amíg egyik sem fogyott még el

        if (t1[i1] >= t2[i2]) {
            t3[n3] = t1[i1];
            i1--;
            n3++;
        }
        else {
            t3[n3] = t2[i2];
            i2++;
            n3++;
        }
    }

    while (i1 >= 0) {
       t3[n3] = t1[i1];
       i1--;
       n3++;
    }

    while (i2 < n2) {
       t3[n3] = t2[i2];
       i2++;
       n3++;
    }

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

Gyakorlatok:

1.

Az A és B növekvő sorrendbe rendezett tömbök az alábbi elemekkel rendelkeznek:

    A=(3,20,25,26,2025);
    B=(x,y,z).

Ahhoz, hogy a növekvő sorrendbe történő összefésülésük eredményét meghatározzuk, az x-et két darab A-beli elemmel kellett összehasonlítsuk, az y-t egyetlen A-beli elemmel, z-t pedig négy darab A-beli elemmel.

Adjuk meg az x, y és z egy-egy lehetséges értékét!

Megoldás:

    x = 10,  y = 15,  z = 30

    A=(3,20,25,26,2025)
                        ^
    B=(x,y,z)
           ^

     3 vs. x    -> x > 3 kell legyen
     20 vs. x   -> x < 20 kell legyen
     20 vs. y   -> x < y < 20 kell legyen
     20 vs. z   -> z > 20 kell
     25 vs. z   -> z > 25
     26 vs. z   -> z > 26
     2025 vs. z

        jó bármilyen z > 26