10.3. Sortarea cu listă de frecvențe

Lista de frecvențe nu compară elementele între ele. Ea numără de câte ori apare fiecare valoare.

Dacă valorile sunt note între 1 și 10, putem folosi frecventa[nota] pentru a memora numărul aparițiilor. După numărare, parcurgem valorile 1, 2, ..., 10 și reconstruim lista sortată.

Condiția esențială

Metoda este potrivită când domeniul valorilor este mic și cunoscut. Dacă avem puține elemente, dar miliarde de valori posibile, o listă de frecvențe poate ocupa multă memorie inutil.

Imaginează-ți că avem 10 casete, numerotate de la 1 la 10. Pentru fiecare valoare citită, punem un semn în caseta corespunzătoare. Nu mutăm valorile între ele în această etapă; doar numărăm de câte ori apare fiecare valoare.

Construim frecvențele:

valori = [5, 3, 5, 2, 3]
frecventa = [0] * 11

for x in valori:
    frecventa[x] += 1

print(frecventa)

Reconstruim lista sortată:

sortata = []
for x in range(1, 11):
    for k in range(frecventa[x]):
        sortata.append(x)

print(sortata)

Poziția 0 este neutilizată, astfel încât indicele coincide cu valoarea notei.

Algoritm Frecvente
citește n și lista a
creează frecventa pentru toate valorile posibile
pentru fiecare x din a execută
    frecventa[x] ← frecventa[x] + 1
sfârșit pentru
pentru x în domeniul valorilor, în ordine crescătoare, execută
    repetă frecventa[x] ori
        scrie x / adaugă x în lista sortată
    sfârșit repetă
sfârșit pentru
SFÂRȘIT ALGORITM

• Dimensiunea listei de frecvențe depinde de domeniul valorilor, nu de numărul de elemente.
• Pentru note 1–10, 11 poziții permit folosirea directă a valorii ca indice, cu poziția 0 neutilizată.
• Pentru un interval [minim,maxim], putem folosi o deplasare față de minim.
• Valorile repetate sunt tratate prin creșterea frecvenței.
• Nu confunda valoarea cu frecvența ei.

Problemă

La un test, n elevi au obținut note întregi între 1 și 10. Sortează notele crescător folosind o listă de frecvențe.

Analiză

Date de intrare: n și n note din [1,10]. Date de ieșire: notele în ordine crescătoare. Numărăm fiecare notă, apoi parcurgem domeniul 1–10 și reconstruim lista.

Python

n = int(input())
frecventa = [0] * 11

for i in range(n):
    nota = int(input())
    frecventa[nota] += 1

sortata = []
for nota in range(1, 11):
    for k in range(frecventa[nota]):
        sortata.append(nota)

print(sortata)

Urmărirea variabilelor

Pentru [8,5,10,5,7], avem frecventa[5]=2, frecventa[7]=1, frecventa[8]=1, frecventa[10]=1. Reconstrucția produce [5,5,7,8,10].

Testarea

Caz normal: [8,5,10,5,7]; caz-limită: [6]; caz particular: toate notele 10; toate notele egale; fiecare notă apare o singură dată.

Justificarea soluției

Fiecare element incrementează exact o singură dată frecvența valorii sale. Parcurgerea domeniului în ordine crescătoare și repetarea fiecărei valori conform frecvenței produce toate valorile, în ordinea cerută. Pentru domeniu de dimensiune m, timpul este O(n+m), iar memoria suplimentară este O(m).

1. Sortează [4,2,4,1,3] cu frecvențe pentru valorile 1–4.
2. Sortează notele [7,10,5,7,9,5,8].
3. Construiește frecvențele pentru valorile 0–5.
4. Afișează numai valorile care apar cel puțin de două ori.
5. Reconstruiește lista sortată fără o metodă de sortare predefinită.

1. Pentru valori din [100,105], construiește frecvențele folosind un domeniu deplasat.
2. Explică de ce frecvențele sunt nepotrivite pentru valori între 0 și 10^9 când n este mic.
3. Estimează memoria pentru un domeniu de 1 000 000 de valori.
4. Sortează o listă de note și afișează frecvența fiecărei note.
5. Compară frecvențele cu selecția minimului pentru n=200 și note 1–10.