Rendezések

Tömbök rendezése

A rendezés azt jelenti, hogy megtartjuk az össszes elemet, de ezek sorrendjét megváltoztatjuk (valamilyen szempont szerint)

Pl. Rendezzük növekvő sorrendbe a

    13 7 8.5 0 2 2

számokat!

    Válasz: 0 2 2 7 8.5 13

Alapfeladat:

Adott n és egy n elemű tömb. Rendezzük át az elemeket a tömbben úgy, hogy növekvő sorrendben legyenek!

1. algoritmus: Selection sort

Minden körben a hátralevő rész legkisebb elemét behozzuk ennek a bal oldalára.

Példa:

    13 7 8 0 2 2
    0 7 8 13 2 2
    0 2 8 13 7 2
    0 2 2 13 7 8
    0 2 2 7 13 8
    0 2 2 7 8 13

 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

#include <iostream>
using namespace std;

int main()
{
    int n;
    cin >> n;

    int t[1000];
    for (int i = 0; i < n; i++)
        cin >> t[i];

    // selection sort
    for (int i = 0; i <= n-2; i++) {
        // i - innen kezdjük a minimumkeresést
        int min_ertek = t[i];
        int min_indexe = i;

        for (int j = i+1; j < n; j++) {
            if (t[j] < min_ertek) {
                min_ertek = t[j];
                min_indexe = j;
            }
        }

        if (min_indexe != i) {
            // csere: t[i] <-> t[min_indexe]
            int masik = t[i];
            t[i] = t[min_indexe];
            t[min_indexe] = masik;
        }
    }

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

    return 0;
}

Más lehetőség a cserére (segédváltozó nélkül):

    a = ..., b = ...

    a = a+b;
    b = a-b;
    a = a-b;

Animáció (itt csere helyett költöztetik az összes elemet).

Feladat: Rendezzünk csökkenő sorrendbe selection sorttal!

 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

#include <iostream>
using namespace std;

int main()
{
    int n;
    cin>>n;
    int t[100];
    for(int i=0;i<n;i++){
        cin>>t[i];
    }
    for(int i=0;i<n-1;i++){
        int maximum=t[i];
        int index=i;
        for(int j=i+1;j<n;j++){
            if(t[j]>maximum){
                maximum=t[j];
                index=j;
            }
        }
        // int vodor=t[index];
        // a = t[index]
        // b = t[i]
        if(index != i){
            t[index]=t[i]+t[index];
            t[i]=t[index]-t[i];
            t[index]=t[index]-t[i];
        }
    }
    for(int i=0;i<n;i++){
        cout<<t[i]<<" ";
    }
    cout<<endl;

    return 0;
}

2. algoritmus: Exchange sort (felcseréléses rendezés)

 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

#include <iostream>
using namespace std;

int main()
{
    int n;
    cin >> n;

    int t[1000];
    for (int i = 0; i < n; i++)
        cin >> t[i];

    for (int i = 0; i < n; i++) {
        for (int j = i+1; j < n; j++) {
            if (t[i] > t[j]) { // ha rossz a sorrend
                int temp = t[i];
                t[i] = t[j];
                t[j] = temp;
            }
        }
    }

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

    return 0;
}

Kövessük nyomon a futását (például n = 5, a tömb pedig: { 10, 2, 3, 20, 8 })! Mi a hasonlóság az exchange sort és a selection sort között?

A hasonlóság, hogy itt is minden körben a háralevő elemek közül a legkisebb kerül balra.

Feladatok

1.

Adott tömb elemeit rendezzük csökkenő sorrendbe exchange sort-tal.

Ötlet: az if-ben > helyett < jel kell (ekkor rossz a sorrend).

2.

Adott tömb elemeit rendezzük az utolsó számjegy szerinti növekvő sorrendbe (azonos utolsó számjegyek esetén pedig érték szerinti csökkenő sorrendbe).

Ötlet: a „mikor rossz a sorrend feltétel” valahogy így fog kinézni:

    if (t[i] utolsó számjegye > t[j] utolsó számjegye
        || (az utolsó számjegyek egyenlők && t[i] < t[j]))

Vagyis:

    if (t[i] % 10 > t[j] % 10
        || (t[i] % 10 == t[j] % 10 && t[i] < t[j]))

3.

Beolvasunk számpárokat, melyek pontok koordinátái. Rendezzük őket az origótól mért távolságuk szerinti növekvő sorrendbe (két tömböt kell rendezni párhuzamosan: x[], y[]).

Ötlet: a beolvasáskor feltöltjük a két tömböt, majd összehasonlításkor az origótól mért távolságokat (vagy egyenesen azok négyzeteit hasonlítjuk össze egymással):

    if ((x[i]*x[i] + y[i]*y[i]) /*megfelelő reláció*/ (x[j]*x[j] + y[j]*y[j]))

 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

#include <iostream>
#include <fstream>
using namespace std;

int main()
{
    ifstream be("input.txt");

    int n;
    be >> n;

    double x[1000], y[1000];
    for (int i = 0; i < n; i++)
        be >> x[i] >> y[i];

    for (int i = 0; i < n; i++) {
        for (int j = i+1; j < n; j++) {
            if ((x[i]*x[i] + y[i]*y[i]) >
                (x[j]*x[j] + y[j]*y[j])
            ) {
                // ha rossz a sorrend, cserélünk
                double temp = x[i];
                x[i] = x[j];
                x[j] = temp;

                temp = y[i];
                y[i] = y[j];
                y[j] = temp;
            }
        }
    }

    // kiírás
    for (int i = 0; i < n; i++)
        cout << x[i] << " " << y[i] << endl;

    return 0;
}

3. algoritmus: Bubble sort (buborékrendezés)

Két-két szomszédos elemet hasonlítunk. Ha rossz sorrendben vannak, felcseréljük és így végigmegyünk a tömbön.

Addig ismételjük a végigjárást, amíg lesz olyan kör, melyben csere nélkül érünk végig.

Példa (növekvő sorrendbe rendezünk, szögletes zárójel határolja azt az elempárt, amit éppen összehasonlítunk):

    [13   7]  8   0   2   2
      7 [13   8]  0   2   2
      7   8 [13   0]  2   2
      7   8   0 [13   2]  2
      7   8   0   2 [13   2]
      7   8   0   2   2  13

    [7  8] 0  2  2  13
     7 [8  0] 2  2  13
     7  0 [8  2] 2  13
     7  0  2 [8  2] 13
     7  0  2  2 [8  13]

    [7  0] 2  2  8  13
     0 [7  2] 2  8  13
     0  2 [7  2] 8  13
     0  2  2 [7  8] 13
     0  2  2  7 [8  13]

    [0  2] 2  7  8  13
     0 [2  2] 7  8  13
     0  2 [2  7] 8  13
     0  2  2 [7  8] 13
     0  2  2  7 [8  13]
     nem volt csere

Más példa:

    1 3 2 5 9 8
    
    [1  3] 2  5  9  8
     1 [3  2] 5  9  8
     1  2 [3  5] 9  8
     1  2  3 [5  9] 8
     1  2  3  5 [9  8]
     1  2  3  5  8  9

    [1  2] 3  5  8  9
     1 [2  3] 5  8  9
     1  2 [3  5] 8  9
     1  2  3 [5  8] 9
     1  2  3  5 [8  9]
     nem volt csere

Implementáció:

 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

#include <iostream>
using namespace std;

int main()
{
    int n;
    cin >> n;

    int t[1000];
    for (int i = 0; i < n; i++)
        cin >> t[i];

    bool volt_csere = true;

    while (volt_csere) {
        volt_csere = false;

        for (int i = 0; i <= n-2; i++) {
            if (t[i] > t[i+1]) {
                int temp = t[i];
                t[i] = t[i+1];
                t[i+1] = temp;

                volt_csere = true;
            }
        }
    }

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

    return 0;
}

4. algoritmus: Insertion sort (beszúró rendezés)

HF plusz pontért: megérteni (hogy működik, miért helyes), bemutatni és implementálni az algoritmust

Alapötlet:

Minden körben az eddigi rendezett részbe egy újabb elemet akarunk betenni, ezért addig cseréljük az előtte levővel, amíg a sorrend helyre nem áll.

Implementáció:

 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

#include <iostream>
using namespace std;

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

    for(int i = 1; i < n; i++){
        int temp = t[i];
        int j = i - 1;
        
        while(j >= 0 && t[j] > temp){
            t[j+1] = t[j];
            j--;
        }
        
        t[j+1] = temp;
    }

    for (int i = 0; i < n; i++)
        cout << t[i] << " ";
    
    cout << endl;
    return 0;
}