|

Algoritmul de Interclasare (Merge Sort) 17


1. Obiectivele lecției:

  • Să înțeleagă principiul interclasării.
  • Să implementeze algoritmul de interclasare (Merge Sort) în limbajul C++.
  • Să analizeze complexitatea algoritmului.
  • Să aplice metoda pentru rezolvarea unor probleme practice.

2. Conținutul lecției:

Ce este interclasarea?

  • Definiție: Interclasarea este o tehnică de combinare a două sau mai multe secvențe ordonate într-o secvență unică, de asemenea ordonată.
  • Aplicație: Interclasarea este folosită în algoritmul Merge Sort, un algoritm de sortare bazat pe divizare și combinare.

Algoritmul Merge Sort:

  1. Divizare: Împarte lista în două părți aproximativ egale.
  2. Sortare: Sortează recursiv fiecare sublistă.
  3. Interclasare: Combină cele două subliste sortate într-o singură listă sortată.

Pseudocod pentru Merge Sort:

Funcție mergeSort(lista):

    Dacă dimensiunea listei <= 1:

        Returnează lista

    Împarte lista în două subliste: stânga și dreapta

    stânga_sortată = mergeSort(stânga)

    dreapta_sortată = mergeSort(dreapta)

    Returnează merge(stânga_sortată, dreapta_sortată)

Funcție merge(stânga, dreapta):

    Creează o listă goală pentru rezultat

    Cât timp există elemente în ambele liste:

        Dacă primul element din stânga <= primul element din dreapta:

            Adaugă elementul din stânga în rezultat

        Altfel:

            Adaugă elementul din dreapta în rezultat

    Adaugă elementele rămase din stânga sau dreapta

    Returnează lista rezultat


3. Cod în C++:


Exemplu complet: Merge Sort

#include <iostream>

using namespace std;

// Funcție pentru interclasare

void merge(int arr[], int left, int mid, int right) {

    int n1 = mid – left + 1; // Dimensiunea primei jumătăți

    int n2 = right – mid;    // Dimensiunea celei de-a doua jumătăți

    // Creează tablouri temporare

    int L[n1], R[n2];

    // Copiază datele în tablourile temporare

    for (int i = 0; i < n1; i++) {

        L[i] = arr[left + i];

    }

    for (int j = 0; j < n2; j++) {

        R[j] = arr[mid + 1 + j];

    }

    // Interclasarea tablourilor temporare

    int i = 0, j = 0, k = left;

    while (i < n1 && j < n2) {

        if (L[i] <= R[j]) {

            arr[k] = L[i];

            i++;

        } else {

            arr[k] = R[j];

            j++;

        }

        k++;

    }

    // Copiază elementele rămase din L, dacă există

    while (i < n1) {

        arr[k] = L[i];

        i++;

        k++;

    }

    // Copiază elementele rămase din R, dacă există

    while (j < n2) {

        arr[k] = R[j];

        j++;

        k++;

    }

}

// Funcție pentru Merge Sort

void mergeSort(int arr[], int left, int right) {

    if (left < right) {

        int mid = left + (right – left) / 2;

        // Sortează recursiv fiecare jumătate

        mergeSort(arr, left, mid);

        mergeSort(arr, mid + 1, right);

        // Interclasează cele două jumătăți sortate

        merge(arr, left, mid, right);

    }

}

// Funcție pentru afișarea array-ului

void printArray(const int arr[], int size) {

    for (int i = 0; i < size; i++) {

        cout << arr[i] << ” „;

    }

    cout << endl;

}

int main() {

    int arr[] = {38, 27, 43, 3, 9, 82, 10};

    int n = sizeof(arr) / sizeof(arr[0]);

    cout << „Array initial: „;

    printArray(arr, n);

    mergeSort(arr, 0, n – 1);

    cout << „Array sortat: „;

    printArray(arr, n);

    return 0;

}


4. Complexitatea algoritmului:

  1. Timp:
    • Cazul cel mai favorabil: O(nlog⁡n)
    • Cazul cel mai defavorabil: O(nlog⁡n)
    • Cazul mediu: O(nlog⁡n)
    • Algoritmul utilizează divizarea recursivă (log⁡n\log n) și combinarea (n).
  2. Spațiu:
    • Necesită spațiu suplimentar pentru vectorii temporari (O(n)).

Avantaje:

  • Stabil (păstrează ordinea relativă a elementelor egale).
  • Eficient pentru liste mari.

Dezavantaje:

  • Necesită spațiu suplimentar.
  • Mai complex de implementat comparativ cu alte metode simple (ex. Bubble Sort).

5. Activități practice pentru elevi:

  1. Modificați algoritmul pentru a sorta în ordine descrescătoare.
  2. Implementați Merge Sort pentru un array de numere reale.
  3. Realizați un program care folosește Merge Sort pentru a sorta numerele unui vector citit de la tastatură.

6. Scheme logice:

  1. Merge Sort:
    • Start -> Împarte array-ul în două -> Sortează recursiv fiecare jumătate -> Interclasează jumătățile -> Stop.
  2. Funcția Merge:
    • Start -> Creează vectorii temporari -> Compară și combină elementele -> Adaugă elementele rămase -> Stop.

7. Concluzie:

  • Algoritmul de interclasare este unul dintre cei mai eficienți algoritmi de sortare pentru liste mari.
  • Este ideal pentru aplicații care necesită stabilitate și complexitate predictibilă.
  • Elevii vor învăța concepte precum divizarea recursivă și combinarea ordonată a datelor.

Similar Posts

Lasă un răspuns

Adresa ta de email nu va fi publicată. Câmpurile obligatorii sunt marcate cu *