Algoritmi de Sortare – Sortarea prin Inserție 14
1. Obiectivele lecției:
- Să înțeleagă principiul sortării prin inserție (Insertion Sort).
- Să implementeze algoritmul în limbajul C++.
- Să analizeze complexitatea algoritmului.
- Să aplice sortarea prin inserție pentru rezolvarea unor probleme practice.
2. Conținutul lecției:
Ce este sortarea prin inserție?
- Definiție: Sortarea prin inserție este un algoritm care construiește lista sortată pe măsură ce parcurge elementele nesortate, inserând fiecare element la poziția sa corectă în lista sortată.
- Principiu: Compară elementul curent cu toate elementele din partea sortată a listei și îl inserează la locul potrivit.
Cum funcționează?
- Consideră primul element sortat.
- Parcurge restul elementelor din lista nesortată.
- Pentru fiecare element, compară-l cu elementele din lista sortată și mută elementele mai mari pentru a face loc.
- Inserează elementul curent la poziția corectă.
Pseudocod:
Intrare: Lista de n elemente
Pentru i de la 1 la n-1:
Elementul curent = lista[i]
j = i – 1
Cât timp j >= 0 și lista[j] > Elementul curent:
lista[j + 1] = lista[j]
j = j – 1
lista[j + 1] = Elementul curent
Ieșire: Lista sortată
3. Cod în C++:
Exemplu 1: Sortare crescătoare
#include <iostream>
using namespace std;
void insertionSort(int arr[], int n) {
for (int i = 1; i < n; i++) {
int current = arr[i];
int j = i – 1;
// Mută elementele mai mari decât current la dreapta
while (j >= 0 && arr[j] > current) {
arr[j + 1] = arr[j];
j–;
}
// Inserează elementul curent la poziția corectă
arr[j + 1] = current;
}
}
void printArray(int arr[], int n) {
for (int i = 0; i < n; i++) {
cout << arr[i] << ” „;
}
cout << endl;
}
int main() {
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr) / sizeof(arr[0]);
cout << „Array initial: „;
printArray(arr, n);
insertionSort(arr, n);
cout << „Array sortat crescator: „;
printArray(arr, n);
return 0;
}
Exemplu 2: Sortare descrescătoare
#include <iostream>
using namespace std;
void insertionSortDescending(int arr[], int n) {
for (int i = 1; i < n; i++) {
int current = arr[i];
int j = i – 1;
// Mută elementele mai mici decât current la dreapta
while (j >= 0 && arr[j] < current) {
arr[j + 1] = arr[j];
j–;
}
// Inserează elementul curent la poziția corectă
arr[j + 1] = current;
}
}
void printArray(int arr[], int n) {
for (int i = 0; i < n; i++) {
cout << arr[i] << ” „;
}
cout << endl;
}
int main() {
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr) / sizeof(arr[0]);
cout << „Array initial: „;
printArray(arr, n);
insertionSortDescending(arr, n);
cout << „Array sortat descrescator: „;
printArray(arr, n);
return 0;
}
4. Complexitatea algoritmului:
- Cazul cel mai defavorabil (O(n²)):
- Lista este ordonată invers.
- Fiecare element trebuie comparat și mutat.
- Cazul cel mai favorabil (O(n)):
- Lista este deja sortată.
- Fiecare element este comparat o singură dată.
- Cazul mediu (O(n²)):
- Lista are o ordine aleatorie.
Avantaje:
- Simplu de implementat.
- Eficient pentru liste mici sau aproape sortate.
- Sortare stabilă (păstrează ordinea relativă a elementelor egale).
5. Activități practice pentru elevi:
- Scrieți un program care sortează un array de numere reale utilizând sortarea prin inserție.
- Realizați un program care sortează un șir de caractere în ordine alfabetică folosind sortarea prin inserție.
- Modificați algoritmul pentru a sorta array-ul crescător pentru elementele pozitive și descrescător pentru cele negative.
6. Scheme logice:
- Sortarea prin inserție:
- Start -> Pentru fiecare element i -> Compară elementul curent cu elementele precedente -> Mută elementele mai mari -> Inserează elementul curent -> Stop.
7. Concluzie:
- Sortarea prin inserție este un algoritm intuitiv și eficient pentru liste mici.
- Este mai rapid decât alte metode simple (cum ar fi sortarea prin selecție) pentru liste aproape sortate.
- Prin implementarea acestui algoritm, elevii vor înțelege mai bine conceptele de comparare și mutare a elementelor.