Algoritmi de Sortare – Sortarea prin Numărare (Counting Sort) 16
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.