Sortarea prin numărare
Toate sortările de până acum compară elemente între ele, iar o sortare prin comparații nu poate coborî sub O(n log n). Dar dacă valorile sunt numere întregi dintr-un interval mic, cum sunt notele de la 1 la 10, poți sorta fără nicio comparație, în O(n + k): pur și simplu numeri câte apariții are fiecare valoare.
Ideea
Profesorul are notele elevilor [7, 10, 4, 7, 9, 10, 5]. În loc să le compare, face un tabel: câte note de 1, câte de 2, ..., câte de 10. Apoi citește tabelul în ordine și scrie fiecare notă de atâtea ori câte apariții are.
note = [7, 10, 4, 7, 9, 10, 5]
frecventa = [0] * 11 # indecșii de la 0 la 10
for nota in note:
frecventa[nota] += 1
for valoare in range(11):
if frecventa[valoare]: Scrie funcția sortare_numarare(note, minim=1, maxim=10) care sortează crescător o listă de numere întregi din intervalul [minim, maxim] prin numărare: o listă de frecvențe, apoi reconstruirea rezultatului. Nu folosi sort() sau sorted().
- Creează frecventa = [0] * (maxim - minim + 1) și numără fiecare valoare la indexul x - minim.
- Parcurge frecvențele în ordine și adaugă fiecare valoare de atâtea ori câte apariții are.
- Trebuie să apară: [4, 5, 7, 7, 9, 10, 10], [1, 1, 1], [], [0, 2, 3, 3].
Restul explicațiilor, editorul și verificarea automată se deblochează cu Recursivitate, backtracking, sortare și căutare binară.

Alex Cristian
Iulian Pahom
Catalina Ioana Dan