Algoritmi de Sortare – Sortarea prin Metoda Bulelor
1. Obiectivele lecției:
- Să înțeleagă principiul metodei de sortare prin bule (Bubble Sort).
- Să implementeze metoda în limbajul C++.
- Să analizeze eficiența algoritmului (complexitatea în timp).
- Să aplice metoda pentru rezolvarea unor probleme practice.
2. Conținutul lecției:
Ce este sortarea prin metoda bulelor?
- Definiție: Sortarea prin metoda bulelor este un algoritm de sortare simplu care compară perechi de elemente adiacente și le interschimbă dacă sunt în ordine greșită, repetând procesul până când lista este sortată.
- Principiu: La fiecare pas, cel mai mare element „urcă” spre poziția sa finală, ca o bulă care se ridică la suprafață.
Pasii metodei:
- Compară fiecare pereche de elemente adiacente din listă.
- Dacă ele sunt în ordine greșită, interschimbă-le.
- Repetă procesul pentru toate elementele, reducând numărul de elemente analizate cu 1 la fiecare iterație (ultimele elemente devin sortate).
- Termină când nu mai există schimbări în timpul unei iterații.
Pseudocod:
Intrare: Lista de n elemente
Pentru i de la 0 la n-1:
Pentru j de la 0 la n-i-2:
Dacă lista[j] > lista[j+1], atunci
Interschimbă lista[j] cu lista[j+1]
Ieșire: Lista sortată
3. Cod în C++:
#include <iostream>
using namespace std;
int main() {
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr) / sizeof(arr[0]);
// Afișarea array-ului inițial
cout << „Array initial: „;
for (int i = 0; i < n; i++) {
cout << arr[i] << ” „;
}
cout << endl;
// Implementarea algoritmului Bubble Sort
for (int i = 0; i < n – 1; i++) {
for (int j = 0; j < n – i – 1; j++) {
if (arr[j] > arr[j + 1]) {
// Interschimbare
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
// Afișarea array-ului sortat
cout << „Array sortat: „;
for (int i = 0; i < n; i++) {
cout << arr[i] << ” „;
}
cout << endl;
return 0;
}
Exemplu 2: Sortare descrescătoare
#include <iostream>
using namespace std;
int main() {
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr) / sizeof(arr[0]);
// Afișarea array-ului inițial
cout << „Array initial: „;
for (int i = 0; i < n; i++) {
cout << arr[i] << ” „;
}
cout << endl;
// Implementarea algoritmului Bubble Sort pentru ordine descrescătoare
for (int i = 0; i < n – 1; i++) {
for (int j = 0; j < n – i – 1; j++) {
if (arr[j] < arr[j + 1]) {
// Interschimbare
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
// Afișarea array-ului sortat descrescător
cout << „Array sortat descrescator: „;
for (int i = 0; i < n; i++) {
cout << arr[i] << ” „;
}
cout << endl;
return 0;
}
4. Complexitatea algoritmului:
- Cazul cel mai defavorabil (O(n²)):
- Lista este ordonată invers față de cea dorită.
- Fiecare pereche trebuie interschimbată.
- Cazul cel mai favorabil (O(n)):
- Lista este deja sortată.
- Algoritmul detectează această situație dacă este optimizat.
- Cazul mediu (O(n²)):
- Lista are o ordine aleatorie.
Optimizare:
Pentru a îmbunătăți algoritmul, se poate introduce o variabilă care detectează dacă au fost efectuate schimbări într-o iterație. Dacă nu există schimbări, algoritmul se oprește.
Cod optimizat:
void bubbleSortOptimized(int arr[], int n) {
bool swapped;
for (int i = 0; i < n – 1; i++) {
swapped = false;
for (int j = 0; j < n – i – 1; j++) {
if (arr[j] > arr[j + 1]) {
// Interschimbare
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true;
}
}
// Dacă nu s-au făcut schimbări, lista este deja sortată
if (!swapped) break;
}
}
5. Activități practice pentru elevi:
- Scrieți un program care sortează un array de numere reale utilizând metoda bulelor.
- Realizați un program care sortează un șir de caractere folosind aceeași metodă.
- Modificați algoritmul pentru a sorta array-ul astfel încât să fie sortat crescător pentru elementele pare și descrescător pentru cele impare.
6. Scheme logice:
- Schema generală Bubble Sort:
- Start -> Pentru fiecare element i -> Pentru fiecare element j -> Compară și interschimbă arr[j]>arr[j+1] -> Terminare -> Stop.
- Schema optimizată:
- Start -> Inițializează swapped = false -> Compară și interschimbă -> Dacă swapped == false -> Terminare -> Stop.
7. Concluzie:
- Sortarea prin metoda bulelor este un algoritm simplu de înțeles, dar mai puțin eficient pentru liste mari.
- Este potrivit pentru situații în care numărul de elemente este mic sau când simplitatea implementării este mai importantă decât eficiența.
- Elevii vor înțelege mai bine conceptele de comparare, interschimbare și iterație.
Algoritmi de Sortare – Sortarea prin Inserție
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.
Algoritmi de Sortare – Sortarea prin Selecția Minimului
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.
Algoritmi de Sortare – Sortarea prin Numărare (Counting Sort)
1. Obiectivele lecției:
- Să înțeleagă principiul sortării prin numărare (Counting Sort).
- Să implementeze algoritmul în limbajul C++.
- Să analizeze complexitatea și aplicațiile algoritmului.
- Să aplice sortarea prin numărare pentru rezolvarea unor probleme practice.
2. Conținutul lecției:
Ce este sortarea prin numărare?
- Definiție: Sortarea prin numărare este un algoritm eficient de sortare pentru liste cu valori discrete (numere întregi mici sau elemente ce pot fi mapate la întregi). Algoritmul funcționează numărând aparițiile fiecărui element și utilizând această informație pentru a poziționa elementele sortate.
- Principiu: Creează un tablou auxiliar pentru a număra frecvența fiecărui element și apoi reconstruiește lista sortată pe baza acestei frecvențe.
Cum funcționează?
- Găsește cel mai mare și cel mai mic element din listă.
- Creează un tablou auxiliar (count) care să stocheze frecvențele fiecărui element.
- Parcurge lista inițială și actualizează frecvențele în count.
- Reconstruiește lista sortată folosind tabloul count.
Pseudocod:
Intrare: Lista de n elemente, valoare_maximă
Creează un tablou count de dimensiune valoare_maximă + 1
Initializează count[i] = 0 pentru toate valorile i
Pentru fiecare element x din lista:
Increment count[x]
Reconstruiește lista sortată:
Pentru i de la 0 la valoare_maximă:
Adaugă count[i] copii ai valorii i în lista sortată
Ieșire: Lista sortată
3. Cod în C++:
Exemplu: Sortare crescătoare
#include <iostream>
using namespace std;
int main() {
int arr[] = {4, 2, 2, 8, 3, 3, 1};
int n = sizeof(arr) / sizeof(arr[0]);
// Găsirea valorii maxime
int maxValue = arr[0];
for (int i = 1; i < n; i++) {
if (arr[i] > maxValue) {
maxValue = arr[i];
}
}
// Crearea tabloului de numărare
int count[maxValue + 1] = {0};
// Numărarea frecvenței fiecărui element
for (int i = 0; i < n; i++) {
count[arr[i]]++;
}
// Reconstruirea array-ului sortat
int index = 0;
for (int i = 0; i <= maxValue; i++) {
while (count[i] > 0) {
arr[index++] = i;
count[i]–;
}
}
// Afișarea array-ului sortat
cout << „Array sortat crescator: „;
for (int i = 0; i < n; i++) {
cout << arr[i] << ” „;
}
cout << endl;
return 0;
}
Exemplu: Sortare descrescătoare
#include <iostream>
using namespace std;
int main() {
int arr[] = {4, 2, 2, 8, 3, 3, 1};
int n = sizeof(arr) / sizeof(arr[0]);
// Găsirea valorii maxime
int maxValue = arr[0];
for (int i = 1; i < n; i++) {
if (arr[i] > maxValue) {
maxValue = arr[i];
}
}
// Crearea tabloului de numărare
int count[maxValue + 1] = {0};
// Numărarea frecvenței fiecărui element
for (int i = 0; i < n; i++) {
count[arr[i]]++;
}
// Reconstruirea array-ului sortat descrescător
int index = 0;
for (int i = maxValue; i >= 0; i–) {
while (count[i] > 0) {
arr[index++] = i;
count[i]–;
}
}
// Afișarea array-ului sortat
cout << „Array sortat descrescator: „;
for (int i = 0; i < n; i++) {
cout << arr[i] << ” „;
}
cout << endl;
return 0;
}
4. Complexitatea algoritmului:
- Cazul cel mai favorabil, mediu și defavorabil: O(n+k), unde:
- n: numărul de elemente din listă.
- k: intervalul de valori (diferența dintre valorile maximă și minimă).
Avantaje:
- Foarte eficient pentru liste mici cu interval de valori redus.
- Stabil (menține ordinea relativă a elementelor egale).
Dezavantaje:
- Ineficient pentru liste cu interval mare de valori, deoarece necesită memorie suplimentară.
- Nu este potrivit pentru valori neîntregi (de exemplu, numere reale).
5. Activități practice pentru elevi:
- Scrieți un program care sortează notele elevilor (între 1 și 10) folosind sortarea prin numărare.
- Modificați algoritmul astfel încât să afișeze doar frecvența fiecărei note fără să reconstruiască lista.
- Realizați un program care sortează în ordine alfabetică caracterele dintr-un șir de caractere folosind sortarea prin numărare.
6. Scheme logice:
- Sortarea prin numărare:
- Start -> Creează tabloul de frecvențe -> Completează tabloul cu frecvențele elementelor -> Reconstruiește lista sortată -> Stop.
7. Concluzie:
- Sortarea prin numărare este un algoritm rapid și simplu pentru liste mici cu valori discrete.
- Este folosită frecvent în aplicații unde stabilitatea și eficiența sunt importante, iar intervalul de valori este limitat.
- Prin implementarea acestui algoritm, elevii vor înțelege concepte precum frecvența și utilizarea tabelelor auxiliare.