[C++] Sortare prin interclasare

[AIM RaJa]

Sortarea a doi vector prin interclasare are ca rezultat un vector sortat crescator, ce contine elementele din ambii vectori.

 

Exemplu:

N = 5

A[1] = 1, A[2] = 3, A[3] = 5, A[4] = 7, A[5] = 9

M = 4

B[1] = 2, B[2] = 4, B[3] = 6, B[4] = 8

 

Rezultatul este vectorul C cu K = N + M = 9 elemente (A[1], B[1], A[2], B[2], A[3], B[3], A[4], B[4], A[5])

 

Sortarea prin interclasare, varianta clasica

O mica explicatie a algoritmului: Se pleaca de la primii doi termeni din cei doi vectori A si B, iar la fiecare pas, alegem mereu elementul cu valoare mai mica, dupa care trecem la urmatorul termen din sirul curent.

 

Daca A < B[j], alegem A si i++;

Daca A > B[j], alegem B[j] si j++;

#include <iostream>

using namespace std;

int N, M, A[100], B[100], C[200];

void Read();
void Interclasare();
void Print();

int main() {
    Read();
    Interclasare();
    Print();

    return 0;
}

void Read() {
    cout << "Atentie ! Vectorii A si B trebuie sa fie deja sortati crescator !\n";

    cout << "N = ";cin >> N;
    for(int i = 1; i <= N; ++i) {
        cout << "A[" << i << "] = ";cin >> A[i];
    }

    cout << "M = ";cin >> M;
    for(int i = 1; i <= M; ++i) {
        cout << "B[" << i << "] = ";cin >> B[i];
    }
}

void Interclasare() {
    int x = 1, y = 1;

    while(x <= N || y <= M) {
        if(x <= N && y <= M) {
            if(A[x] < B[y]) {
                C[++C[0]] = A[x];
                ++x;
            }
            else {
                C[++C[0]] = B[y];
                ++y;
            }
        }
        else {
            if(x <= N) {
                C[++C[0]] = A[x];
                ++x;
            }
            else {
                C[++C[0]] = B[y];
                ++y;
            }
        }
    }
}

void Print() {
    cout << "C: ";

    for(int i = 1; i <= C[0]; ++i) {
        cout << C[i] << ' ';
    }

    cout << '\n';
}

Pentru intrebari, sugestii, neclaritati, lasati un reply in acest topic.

[Cdorsu]

Sincer, nu prea imi plac metodele astea de sortare.

Prefer qsort sau sort.

 

Oricum, tutorialul mi se pare bun. Eu de ce n-am facut asa ceva la scoala, pana acum?

[AIM RaJa]

@@Cdorsu, intr-adevar, sort, qsort si radix sort sunt cele mai rapide metode posibile de sortare. Insa e bine sa cunosti cat mai multi algoritmi, nu stii cand te pot ajuta Bubble sort, Interclasare, Sortare prin numarare, Brute sort etc. Legat de faza cu scoala, depinde foarte mult si de profesor. Nu toti profesorii se ocupa la fel de elevii lor. De obicei, acestia le dau, ca sa spun asa "start-ul" in obiectul care-l predau, urmand ca elevul sa afle singur anumite informatii. Eu personal, interclasarea am invatat-o de pe net, singur. Nu e foarte complicata. Si poti sorta si un singur sir prin interclasare. Il imparti in jumatate, dupa fiecare jumatate o mai imparti in cate o jumatate (adica sfert) si tot asa, pana ajungi la siruri de cate doua elemente, ca mai apoi sa compari primul element din fiecare sir.

[ALexu]

Topic closed !