Interclasare – Un algoritm eficient în C++

Introducere

În lumea programării, interclasarea este un proces esențial în sortarea eficientă a datelor. Algoritmul de interclasare combină două sau mai multe liste de elemente sortate într-o singură listă, astfel încât rezultatul final să fie, de asemenea, sortat.

Implementarea algoritmului de interclasare în C++

Pentru a implementa algoritmul de interclasare în C++, putem folosi o abordare recursivă sau una iterativă. În acest exemplu, vom utiliza abordarea recursivă.

#include <iostream>
using namespace std;

void interclasare(int arr[], int stanga, int mijloc, int dreapta) {
    int i, j, k;
    int n1 = mijloc - stanga + 1;
    int n2 = dreapta - mijloc;

    int L[n1], R[n2];

    for (i = 0; i < n1; i++)
        L[i] = arr[stanga + i];
    for (j = 0; j < n2; j++)
        R[j] = arr[mijloc + 1 + j];

    i = 0;
    j = 0;
    k = stanga;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        }
        else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }

    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

void mergeSort(int arr[], int stanga, int dreapta) {
    if (stanga < dreapta) {
        int mijloc = stanga + (dreapta - stanga) / 2;

        mergeSort(arr, stanga, mijloc);
        mergeSort(arr, mijloc + 1, dreapta);

        interclasare(arr, stanga, mijloc, dreapta);
    }
}

void afisare(int arr[], int dimensiune) {
    for (int i = 0; i < dimensiune; i++)
        cout << arr[i] << " ";
    cout << endl;
}

int main() {
    int arr[] = { 12, 11, 13, 5, 6, 7 };
    int dimensiune = sizeof(arr) / sizeof(arr[0]);

    cout << "Lista initiala: ";
    afisare(arr, dimensiune);

    mergeSort(arr, 0, dimensiune - 1);

    cout << "Lista sortata: ";
    afisare(arr, dimensiune);

    return 0;
}

Explicarea codului

În codul de mai sus, funcția interclasare primește un vector arr și trei indici: stanga, mijloc și dreapta. Aceasta împarte vectorul în două jumătăți și apoi interclasează cele două jumătăți pentru a forma vectorul sortat final.

Funcția mergeSort este funcția principală care utilizează recursivitatea pentru a împărți vectorul în jumătăți și pentru a apela funcția interclasare pentru a interclasa jumătățile și a le sorta.

Funcția afisare este folosită pentru a afișa vectorul sortat final.

Concluzie

Algoritmul de interclasare este o metodă eficientă de sortare a datelor în C++. Prin combinarea a două sau mai multe liste sortate, putem obține o listă sortată într-un mod optim. Implementarea acestui algoritm ne permite să sortăm cu ușurință orice set de date într-un mod eficient și fiabil.

În concluzie, algoritmul de interclasare este o tehnică valoroasă în lumea programării și poate fi aplicat într-o varietate de scenarii pentru a obține rezultate precise și eficiente.