10.1. Sortarea prin selecția minimului

Sortarea înseamnă așezarea elementelor unei liste într-o ordine stabilită. Pentru numere, cele mai uzuale sunt ordinea crescătoare și ordinea descrescătoare.

Ideea selecției minimului

La fiecare pas, lista este privită ca două zone: în stânga se află partea deja sortată, iar în dreapta partea încă nesortată. Căutăm cel mai mic element din zona nesortată și îl aducem la începutul acesteia.

Dacă suntem la poziția i, căutăm minimul între pozițiile i și n - 1. Variabila poz_min reține poziția minimului, nu valoarea lui.

De ce este necesară interschimbarea?

După ce am identificat minimul, acesta trebuie să ajungă pe poziția i. În Python putem schimba direct două valori prin a[i], a[poz_min] = a[poz_min], a[i].

Imaginează-ți cartonașe cu punctaje așezate pe o masă. Pentru primul loc cauți cel mai mic punctaj dintre toate cartonașele și îl așezi primul. Pentru al doilea loc cauți minimul dintre cartonașele rămase. Repeți până când lista este ordonată.

În Python, schimbarea simultană a două elemente este simplă:

a = [7, 4, 9, 2, 5]
a[0], a[3] = a[3], a[0]
print(a)

Pentru sortare, bucla exterioară stabilește începutul zonei nesortate, iar bucla interioară caută poziția minimului.

a = [7, 4, 9, 2, 5]
n = len(a)

for i in range(n - 1):
    poz_min = i
    for j in range(i + 1, n):
        if a[j] < a[poz_min]:
            poz_min = j
    if poz_min != i:
        a[i], a[poz_min] = a[poz_min], a[i]

print(a)

Algoritm SelectiaMinimului
citește lista a și n
pentru i ← 0, n - 2 execută
    poz_min ← i
    pentru j ← i + 1, n - 1 execută
        dacă a[j] < a[poz_min] atunci
            poz_min ← j
        sfârșit dacă
    sfârșit pentru
    dacă poz_min ≠ i atunci
        interschimbă a[i] cu a[poz_min]
    sfârșit dacă
sfârșit pentru
scrie lista sortată
SFÂRȘIT ALGORITM

• Nu confunda valoarea minimă cu poz_min, care este poziția ei.
• Nu căuta minimul în partea deja sortată.
• Pentru o listă cu un singur element nu este necesară nicio interschimbare.
• Valorile egale nu împiedică sortarea.
• Testarea pe exemple concrete este diferită de justificarea corectitudinii algoritmului.

Problemă

Se citește o listă de n numere întregi. Să se sorteze crescător folosind selecția minimului.

Analiză

Date de intrare: n și cele n valori. Date de ieșire: lista în ordine crescătoare. La fiecare pas determinăm minimul din partea nesortată și îl aducem pe poziția curentă.

Python

n = int(input())
a = []
for i in range(n):
    a.append(int(input()))

for i in range(n - 1):
    poz_min = i
    for j in range(i + 1, n):
        if a[j] < a[poz_min]:
            poz_min = j
    if poz_min != i:
        a[i], a[poz_min] = a[poz_min], a[i]

print(a)

Urmărirea variabilelor

Pentru [7, 4, 9, 2, 5]: la i=0, poz_min=3, rezultă [2,4,9,7,5]; la i=1, minimul este deja 4; la i=2, minimul este 5 și obținem [2,4,5,7,9].

Testarea

• Caz normal: [7,4,9,2,5] → [2,4,5,7,9]
• Caz-limită: [8] → [8]
• Caz particular: [5,5,5,5] → aceeași listă
• Caz deja sortat: [1,2,3,4] → aceeași listă
• Caz descrescător: [5,4,3,2,1] → [1,2,3,4,5]

Justificarea soluției

După pasul i, pozițiile de la 0 la i conțin cele mai mici i+1 elemente, în ordine. Pentru n elemente se fac n(n-1)/2 comparații, deci timpul este de ordin O(n²).

1. Sortează crescător [6, 2, 9, 1, 5].
2. Sortează descrescător o listă folosind selecția maximului.
3. Afișează lista după fiecare interschimbare.
4. Sortează [4, 1, 4, 2, 3] și observă valorile egale.
5. Citește n și n numere și afișează lista sortată crescător.

1. Determină numărul de comparații pentru n=5, n=10 și n=100.
2. Explică de ce selecția minimului face același număr de comparații pentru o listă deja sortată.
3. Modifică algoritmul pentru intervalul de poziții [p,q].
4. Sortează descrescător punctajele și afișează primele 10 valori.
5. Compară numărul de interschimbări pentru [1,2,3,4,5] și [5,4,3,2,1].