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:
- Divizare: Împarte lista în două părți aproximativ egale.
- Sortare: Sortează recursiv fiecare sublistă.
- 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:
- Timp:
- Cazul cel mai favorabil: O(nlogn)
- Cazul cel mai defavorabil: O(nlogn)
- Cazul mediu: O(nlogn)
- Algoritmul utilizează divizarea recursivă (logn\log n) și combinarea (n).
- 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:
- Modificați algoritmul pentru a sorta în ordine descrescătoare.
- Implementați Merge Sort pentru un array de numere reale.
- Realizați un program care folosește Merge Sort pentru a sorta numerele unui vector citit de la tastatură.
6. Scheme logice:
- Merge Sort:
- Start -> Împarte array-ul în două -> Sortează recursiv fiecare jumătate -> Interclasează jumătățile -> Stop.
- 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.