Ce vei învăța astăzi?
După această lecție vei învăța să sortezi o listă prin selecția minimului, înțelegând fiecare pas al algoritmului și implementarea în Python.
Ideea metodei selecției minimului
Definiție: La fiecare pas căutăm minimul din partea nesortată (porțiunea listei încă neordonată) și îl mutăm pe prima poziție a acelei părți. Repetăm până când toate pozițiile sunt complete.
Analogia cu finaliștii unui concurs
Ca la arhivarea finaliștilor unui concurs: la fiecare rundă îl alegi pe cel mai bun dintre concurenții rămași și îl așezi la locul lui, pe podium.
După prima rundă, cel mai bun e pe locul 1. După a doua, următorul cel mai bun e pe locul 2, și tot așa.
Algoritmul pas cu pas
Considerăm lista [7, 3, 9, 1, 5]. Urmărim cum se completează pozițiile unul câte unul:
| Pas | Partea nesortată | Minimul găsit | Lista după interschimbare (schimbarea între ele a două elemente) |
|---|---|---|---|
| 1 | 7 3 9 1 5 | 1 (poziția 3) | 1 3 9 7 5 |
| 2 | 3 9 7 5 | 3 (poziția 1) | 1 3 9 7 5 |
| 3 | 9 7 5 | 5 (poziția 4) | 1 3 5 7 9 |
| 4 | 7 9 | 7 (poziția 3) | 1 3 5 7 9 |
Observă: după n - 1 pași lista este sortată, pentru că la fiecare pas fixăm câte un element pe poziția finală.
Implementarea cu doi indici
Folosim i pentru poziția care trebuie completată și j pentru a parcurge partea nesortată. Variabila p reține poziția minimului găsit (indicele elementului cu valoarea minimă din partea nesortată).
Exemplu: sortare prin selecția minimului
v = [7, 3, 9, 1, 5]
n = len(v)
for i in range(n - 1):
p = i
for j in range(i + 1, n):
if v[j] < v[p]:
p = j
v[i], v[p] = v[p], v[i]
print(v)
Observă: bucla interioară (j) caută minimul, iar apoi o singură linie face interschimbarea: v[i], v[p] = v[p], v[i].
Interschimbarea (swap) în Python
Pentru a schimba între ele două valori a și b scriem a, b = b, a. Python face interschimbarea într-o singură linie, fără variabilă temporară.
Exemplu de interschimbare
a = 5 b = 9 print(a, b) a, b = b, a print(a, b)
Observă: înainte: 5 9. După interschimbare: 9 5.
Exercițiu de completare
Completează descrierea metodei selecției minimului:
La fiecare pas căutăm ______-ul din lista rămasă. Poziția primei părți nesortate este ținută de indicele ______, iar bucla interioară folosește indicele ______. Pentru interschimbare scriem a, b = b, a - aceasta este operația de ______.
Bancă de cuvinte:
Test de înțelegere
Test rapid - selecția minimului:
1. În selecția minimului, la pasul 1 căutăm:
2. După primul pas, minimul se află pe poziția:
3. Interschimbarea a două variabile a și b se scrie în Python:
Test suplimentar - verifică ce ai reținut
Test rapid suplimentar - selecția minimului:
1. La fiecare pas al selecției minimului căutăm:
2. După prima trecere, minimul se află:
3. Interschimbarea valorilor v[i] și v[p] se scrie corect:
i + 1, nu de la 0. Dacă o pornești de la 0, re-cauți elemente deja sortate și poți strica ordinea listei.Aprofundare
Metoda se numește „selecția minimului", dar aceeași idee funcționează și invers: putem căuta maximul la fiecare pas și îl putem pune pe ultima poziție nesortată, obținând tot o sortare crescătoare. Alegerea între minim și maxim depinde doar de conveniență.
- Numărul exact de comparații: bucla interioară execută n-1, apoi n-2, ..., 1 comparații, în total n(n-1)/2, indiferent de datele de intrare. Selecția minimului face întotdeauna acest număr de comparații, chiar dacă lista este deja sortată.
- Numărul de interschimbări: la fiecare pas se face cel mult o interschimbare, deci cel mult n-1 în total - un avantaj față de metoda bulelor.
- Stabilitate: dacă două elemente egale își schimbă pozițiile relative, vorbim de sortare instabilă; pentru numere egale ordinea nu contează, dar la sortarea de înregistrări (nume și note) poate fi relevantă.
- Sortarea descrescătoare: se obține schimbând condiția
v[j] < v[p]înv[j] > v[p]- căutăm maximul. - Valori de alte tipuri: algoritmul compară orice valori comparabile (numere, texte), deci aceeași structură sortează și liste de cuvinte, în ordine alfabetică.
- De ce n-1 pași: după ce am fixat primele n-1 elemente, ultimul rămas este automat pe poziția corectă; un pas suplimentar ar fi inutil.
PbInfo - Sortare prin selecția minimului
Enunț:
Cerință: Se citește numărul natural n și apoi n numere întregi. Să se sorteze crescător vectorul folosind metoda selecției minimului și să se afișeze.
Date de intrare:
Programul citește de la tastatură numărul n, apoi n numere întregi.
Date de ieșire:
Programul va afișa cele n numere sortate crescător, separate prin spații.
Restricții și precizări:
n este un număr natural, cu 1 <= n <= 1000, iar elementele sunt numere întregi.
Exemplu:
Intrare:
5 7 3 9 1 5
Ieșire:
1 3 5 7 9
Cum gândim soluția:
- Citim n și vectorul v cu
list(map(int, input().split())) - Pentru fiecare i de la 0 la n-2 căutăm minimul din partea rămasă
- Reținem poziția minimului în p și facem interschimbarea v[i], v[p] = v[p], v[i]
- Afișăm vectorul sortat
Scrie soluția în Python:
Soluție corectă:
n = int(input())
v = list(map(int, input().split()))
for i in range(n - 1):
p = i
for j in range(i + 1, n):
if v[j] < v[p]:
p = j
v[i], v[p] = v[p], v[i]
for x in v:
print(x, end=" ")
Ce învățăm: folosim două bucle: una pentru poziția de completat (i) și una pentru căutarea minimului (j), plus interschimbarea într-o singură linie.
PbInfo - Minimul și poziția lui
Enunț:
Cerință: Se citește numărul natural n și apoi n numere întregi. Să se afișeze valoarea minimă și prima poziție (index) la care apare.
Date de intrare:
Programul citește de la tastatură numărul n, apoi n numere întregi.
Date de ieșire:
Programul va afișa minimul și indexul primei sale apariții.
Restricții și precizări:
n este un număr natural, cu 1 <= n <= 1000, iar elementele sunt numere întregi.
Exemplu:
Intrare:
5 7 3 9 3 5
Ieșire:
3 1
Cum gândim soluția:
- Citim vectorul v
- Calculăm minimul cu
min(v) - Găsim prima poziție cu
v.index(m)
Scrie soluția în Python:
Soluție corectă:
n = int(input()) v = list(map(int, input().split())) m = min(v) print(m, v.index(m))
Ce învățăm: putem folosi funcțiile predefinite min() și index() pentru a găsi rapid minimul și poziția lui.
Exercițiul Practic: Sortarea prin selecția minimului
Sarcini de lucru
Aplică metoda selecției minimului în programe complete, observând evoluția listei pas cu pas.
Sarcina 1: Sortare cu afișare pas cu pas
Cerință: Scrie un program care citește n numere, le sortează prin selecția minimului și afișează lista după fiecare pas (fiecare interschimbare).
Soluție:
n = int(input())
v = list(map(int, input().split()))
for i in range(n - 1):
p = i
for j in range(i + 1, n):
if v[j] < v[p]:
p = j
v[i], v[p] = v[p], v[i]
print(v)
Verifică: vezi cum fiecare element „se așază" pe poziția finală, un pas pe linie.
Sarcina 2: Minimul fără funcția min
Cerință: Scrie un program care citește n numere și determină minimul manual (fără min()) și poziția primei sale apariții.
Soluție:
n = int(input())
v = list(map(int, input().split()))
m = v[0]
p = 0
for i in range(1, n):
if v[i] < m:
m = v[i]
p = i
print(m, p)
Verifică: parcurgem vectorul o singură dată, actualizând minimul și poziția de fiecare dată când găsim o valoare mai mică.