Algoritmi de Sortare – Sortarea prin Selecția Minimului 15
1. Obiectivele lecției:
- Să înțeleagă principiul sortării prin selecția minimului (Selection Sort).
- Să implementeze algoritmul în limbajul C++.
- Să analizeze complexitatea algoritmului.
- Să aplice metoda pentru rezolvarea unor probleme practice.
2. Conținutul lecției:
Ce este sortarea prin selecția minimului?
- Definiție: Sortarea prin selecția minimului este un algoritm de sortare simplu care găsește cel mai mic element dintr-o listă nesortată și îl aduce la început, repetând procesul pentru restul listei.
- Principiu: La fiecare pas, cel mai mic element din secțiunea nesortată a listei este plasat în poziția sa finală.
Cum funcționează?
- Găsește cel mai mic element din lista nesortată.
- Interschimbă-l cu primul element al listei nesortate.
- Repetă procesul pentru restul listei, reducând secțiunea nesortată cu un element la fiecare pas.
Pseudocod:
Intrare: Lista de n elemente
Pentru i de la 0 la n-1:
minIndex = i
Pentru j de la i+1 la n-1:
Dacă lista[j] < lista[minIndex], atunci
minIndex = j
Interschimbă lista[i] cu lista[minIndex]
Ieșire: Lista sortată
3. Cod în C++:
Exemplu 1: Sortare crescătoare
#include <iostream>
using namespace std;
void selectionSort(int arr[], int n) {
for (int i = 0; i < n – 1; i++) {
int minIndex = i;
// Găsește indexul minimului
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
// Interschimbare
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
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);
selectionSort(arr, n);
cout << „Array sortat crescator: „;
printArray(arr, n);
return 0;
}
Exemplu 2: Sortare descrescătoare
#include <iostream>
using namespace std;
void selectionSortDescending(int arr[], int n) {
for (int i = 0; i < n – 1; i++) {
int maxIndex = i;
// Găsește indexul maximului
for (int j = i + 1; j < n; j++) {
if (arr[j] > arr[maxIndex]) {
maxIndex = j;
}
}
// Interschimbare
int temp = arr[i];
arr[i] = arr[maxIndex];
arr[maxIndex] = temp;
}
}
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);
selectionSortDescending(arr, n);
cout << „Array sortat descrescator: „;
printArray(arr, n);
return 0;
}
4. Complexitatea algoritmului:
- Cazul cel mai defavorabil (O(n²)):
- În fiecare iterație, algoritmul compară toate elementele nesortate pentru a găsi minimul.
- Cazul cel mai favorabil (O(n²)):
- Lista este deja sortată, dar algoritmul continuă să compare toate elementele.
- Cazul mediu (O(n²)):
- Lista are o ordine aleatorie.
Avantaje:
- Simplu de implementat și de înțeles.
- Nu necesită memorie suplimentară (sortare in-place).
Dezavantaje:
- Ineficient pentru liste mari din cauza numărului mare de comparații.
- Nu este un algoritm de sortare stabil (nu 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 selecția minimului.
- Realizați un program care sortează un șir de caractere în ordine alfabetică folosind selecția minimului.
- Modificați algoritmul pentru a sorta un array astfel încât elementele pare să fie sortate crescător și cele impare descrescător.
6. Scheme logice:
- Sortarea prin selecția minimului:
- Start -> Pentru fiecare element i: Găsește minimul în lista nesortată -> Interschimbă minimul cu arr[i] -> Stop.
7. Concluzie:
- Sortarea prin selecția minimului este utilă pentru liste mici sau când simplitatea implementării este mai importantă decât eficiența.
- Prin implementarea acestui algoritm, elevii pot înțelege mai bine conceptele de comparare și interschimbare.
- Este un algoritm fundamental care poate fi extins și optimizat pentru aplicații mai complexe.