Școala Româno-Britanică
Modulul 4 Clasa a IX-a | Python

Ora 9: Sortarea în probleme practice - aplicații

Ce vei învăța astăzi: Sortarea punctajelor unui concurs, ordonarea cererilor după coduri, aplicarea metodelor de sortare în probleme reale

Rezultat practic: Construiești clasamente și liste ordonate pornind de la date reale, alegând metoda de sortare potrivită (Competența 6.2).

Competența 6.2 Săptămâna 22

Înainte de a începe

De ce contează? Aplicațiile reale ale sortării - clasamente, ordonarea cererilor după coduri, registre - sunt cele pe care le vei întâlni în problemele de examen și în proiectul modulului. Aici înveți să alegi metoda potrivită pentru fiecare situație.

Ce știi deja?

Ai învățat selecția minimului cu comparația v[j] < v[p] pentru ordine crescătoare. Ce trebuie schimbat pentru ca lista să fie ordonată descrescător?

Ideea-cheie: Un clasament se obține sortând descrescător, adică căutând maximul la fiecare pas; codurile se sortează ca numere sau lexicografic, cu aceeași structură de selecție.
SINTEZĂ TEORETICĂ ȘI EXEMPLE GHIDATE

Ce vei învăța astăzi?

După această lecție vei învăța să aplici sortarea în probleme din viața reală: să construiești clasamente ale unui concurs, să ordonezi cereri după codurile lor și să alegi metoda potrivită pentru fiecare situație.

Sortarea descrescătoare a punctajelor (ordonarea de la cea mai mare la cea mai mică valoare)
Ordonarea cererilor după coduri
Alegerea metodei potrivite în probleme reale
Programe complete cu citire și afișare

Sortarea punctajelor unui concurs

Definiție: Un clasament este lista participanților ordonată după punctaj, de la cel mai mare la cel mai mic. Pentru a-l obține, sortăm punctajele descrescător (de la valoarea cea mai mare la cea mai mică): la fiecare pas căutăm maximul din partea nesortată și îl punem pe poziția curentă.

Este exact selecția minimului, dar cu comparația inversată: în loc de v[j] < v[p] folosim v[j] > v[p].

De ce ne folosim?

Ca la un concurs școlar: notele de la evaluare se afișează ordonat, de la cea mai mare la cea mai mică, ca să se vadă imediat cine a obținut rezultatul cel mai bun. Orice organizator de concurs are nevoie de un astfel de program.

Clasamentul

Punctaje ordonate descrescător, locul 1 la început

Sortarea

Maximul se așază primul, apoi următorul, și tot așa

Exemplu: clasamentul punctajelor

citește n citește punctaje[1..n] pentru i = 1, n - 1 execută p = i pentru j = i + 1, n execută dacă punctaje[j] > punctaje[p] atunci p = j punctaje[i] <-> punctaje[p] scrie punctaje[1..n]
Python - clasamentul concursului
n = int(input())
punctaje = list(map(int, input().split()))

for i in range(n - 1):
    p = i
    for j in range(i + 1, n):
        if punctaje[j] > punctaje[p]:
            p = j
    punctaje[i], punctaje[p] = punctaje[p], punctaje[i]

for x in punctaje:
    print(x, end=" ")

Observă: pentru punctajele 42 78 55 78 90 programul afișează 90 78 78 55 42. Punctajele egale rămân împreună, iar maximul ajunge primul.

Ordonarea cererilor după coduri

În administrație și comerț, fiecare cerere sau comandă primește un cod (număr sau text). A ordona cererile după coduri înseamnă să sortăm lista de coduri, astfel încât procesarea să se facă într-o ordine clară, fără a rata nimic.

Codurile numerice se compară ca numere; codurile de tip text se compară lexicografic, adică în ordinea alfabetică a caracterelor, exact cum funcționează < pe șiruri în Python.

De ce ne folosim?

Este ca registrul unei biblioteci: cărțile sunt așezate după cota lor, în ordine crescătoare, ca să poată fi găsite imediat. Ordonarea după cod este primul pas spre o căutare rapidă.

Exemplu: sortarea codurilor text

Python - ordonarea codurilor
n = int(input())
coduri = []

for i in range(n):
    coduri.append(input().strip())

for i in range(n - 1):
    p = i
    for j in range(i + 1, n):
        if coduri[j] < coduri[p]:
            p = j
    coduri[i], coduri[p] = coduri[p], coduri[i]

for c in coduri:
    print(c)

Observă: selecția minimului funcționează identic pentru texte: coduri[j] < coduri[p] compară șirurile caracter cu caracter. Metoda strip() elimină spațiile de la capete, pentru a nu altera codul.

Alegerea metodei potrivite în probleme reale

În problemele practice, alegem metoda după tipul datelor:

  • Punctaje sau note într-un interval mic (0-100, 1-10): lista de frecvențe, cea mai rapidă.
  • Valori oricât de mari, numere sau texte: selecția minimului sau metoda bulelor.
  • Clasament descrescător: selecția minimului cu maxim, sau frecvențele parcurse în sens invers.
Situație reală Datele Metoda recomandată
Notele clasei (1-10) Interval mic Lista de frecvențe
Punctaje concurs (0-100) Interval mic Lista de frecvențe, parcurgere inversă
Coduri de cereri (numere mari) Valori dispersate Selecția minimului
Denumiri de produse Texte Selecția minimului sau bulele

Exemplu: clasament cu lista de frecvențe

Python - clasament cu frecvențe
n = int(input())
punctaje = list(map(int, input().split()))
fr = [0] * 101

for x in punctaje:
    fr[x] = fr[x] + 1

for i in range(100, 0, -1):
    for _ in range(fr[i]):
        print(i, end=" ")

Observă: parcurgem pozițiile de la 100 în jos, deci valorile mari apar primele - un clasament descrescător obținut fără nicio interschimbare.

Exercițiu de completare

Completează descrierea clasamentului:

Un clasament este lista punctajelor ordonată ______. Pentru a-l obține cu selecția minimului, căutăm ______ la fiecare pas. Condiția de comparație devine v[j] ______ v[p]. Cu lista de frecvențe, parcurgem pozițiile în sens ______.

Bancă de cuvinte:
descrescător maximul > invers

Exercițiu de completare

Completează despre ordonarea cererilor:

Codurile de tip text se compară ______, caracter cu caracter. Lista de coduri se citește cu ______ într-o buclă. Pentru a elimina spațiile de la capetele codului folosim ______. Codurile numerice mari se sortează cu ______ minimului.

Bancă de cuvinte:
lexicografic append strip selecția

Test de înțelegere

Test rapid - sortarea în probleme practice:

1. Pentru un clasament descrescător cu selecția minimului, condiția de comparație este:

2. Punctaje de la 0 la 100 se sortează cel mai rapid cu:

3. Codurile de tip text se compară:

Ai grijă la: dacă sortezi perechi de date (nume și punctaje) și le muți separat, asociația se pierde. La fiecare interschimbare, mută ambele liste împreună.

Aprofundare

În problemele reale, de multe ori trebuie sortate perechi de date: numele participantului împreună cu punctajul lui. Putem folosi două liste paralele (nume și punctaje) și le mutăm împreună la fiecare interschimbare, astfel încât asocierea să nu se piardă.

  • Liste paralele: dacă punctaje[i] se mută pe poziția p, atunci și nume[i] se mută pe poziția p: punctaje[i], punctaje[p] = punctaje[p], punctaje[i] și la fel pentru nume.
  • Egalități de punctaj: două punctaje egale pot apărea în orice ordine; dacă problema cere o regulă de departajare (de exemplu numele alfabetic), comparăm mai întâi punctajele și, la egalitate, numele.
  • Sortarea după două criterii: condiția devine „punctaj mai mare SAU punctaj egal ȘI nume mai mic" - se scrie cu operatori logici: if pct[j] > pct[p] or (pct[j] == pct[p] and nume[j] < nume[p]).
  • Frecvențele nu rețin numele: lista de frecvențe păstrează doar valorile, nu și informațiile asociate; când trebuie afișat și numele, preferăm selecția minimului pe perechi.
  • Stabilitatea: dacă două cereri au același cod, iar problema cere păstrarea ordinii inițiale, avem nevoie de un criteriu suplimentar (de exemplu data depunerii).
APLICARE ȘI REZOLVARE DE PROBLEME

PbInfo - Clasamentul concursului

Enunț:

Cerință: Se citesc n punctaje obținute de participanții unui concurs. Să se afișeze punctajele în ordine descrescătoare, separate prin spații, pentru a forma clasamentul.

Date de intrare:

Programul citește de la tastatură numărul natural n, apoi n numere naturale, separate prin spații.

Date de ieșire:

Programul va afișa pe o singură linie cele n punctaje în ordine descrescătoare, separate prin spații.

Restricții și precizări:

1 <= n <= 100, iar punctajele sunt numere naturale mai mici sau egale cu 100.

Exemplu:

Intrare:

5
42 78 55 78 90

Ieșire:

90 78 78 55 42
Cum gândim soluția:
  1. Citim n și lista de punctaje cu input().split() transformată cu map(int, ...)
  2. Sortăm descrescător cu selecția minimului, căutând maximul: condiția v[j] > v[p]
  3. Afișăm punctajele pe o singură linie cu end=" "
Scrie soluția în Python:
Soluție corectă:
Soluție Python
n = int(input())
punctaje = list(map(int, input().split()))

for i in range(n - 1):
    p = i
    for j in range(i + 1, n):
        if punctaje[j] > punctaje[p]:
            p = j
    punctaje[i], punctaje[p] = punctaje[p], punctaje[i]

for x in punctaje:
    print(x, end=" ")

Ce învățăm: inversarea comparației transformă selecția minimului într-o sortare descrescătoare - baza oricărui clasament.

PbInfo - Ordonarea codurilor

Enunț:

Cerință: Se citesc n coduri numerice ale unor cereri. Să se afișeze codurile în ordine crescătoare, câte unul pe linie, pentru ca cererile să fie procesate în ordine.

Date de intrare:

Programul citește de la tastatură numărul natural n, apoi n numere naturale, separate prin spații.

Date de ieșire:

Programul va afișa cele n coduri în ordine crescătoare, câte unul pe linie.

Restricții și precizări:

1 <= n <= 100, iar codurile sunt numere naturale mai mici decât 100000.

Exemplu:

Intrare:

4
305 120 450 305

Ieșire:

120
305
305
450
Cum gândim soluția:
  1. Citim n și codurile într-o listă
  2. Sortăm crescător cu selecția minimului
  3. Afișăm fiecare cod cu print(), câte unul pe linie
Scrie soluția în Python:
Soluție corectă:
Soluție Python
n = int(input())
coduri = list(map(int, input().split()))

for i in range(n - 1):
    p = i
    for j in range(i + 1, n):
        if coduri[j] < coduri[p]:
            p = j
    coduri[i], coduri[p] = coduri[p], coduri[i]

for c in coduri:
    print(c)

Ce învățăm: codurile egale se păstrează împreună după sortare, iar afișarea câte unul pe linie respectă formatul cerut de enunț.

EXERCIȚII PRACTICE

Exercițiul Practic: Sortarea în probleme practice

Sarcini de lucru

Aplică metodele de sortare pe date reale: note, punctaje și coduri de cereri.

Sarcina 1: Notele clasei, de la cea mai mare la cea mai mică

Cerință: Scrie un program care citește n note (de la 1 la 10) și le afișează descrescător, folosind lista de frecvențe.

Soluție:
n = int(input())
note = list(map(int, input().split()))
fr = [0] * 11

for x in note:
    fr[x] = fr[x] + 1

for i in range(10, 0, -1):
    for _ in range(fr[i]):
        print(i, end=" ")

Verifică: pentru notele 7 5 9 5 8 7 10 5 se afișează 10 9 8 7 7 5 5 5.

Sarcina 2: Punctaje și nume paralele

Cerință: Scrie un program care citește n perechi (nume, punctaj) și afișează numele în ordinea descrescătoare a punctajelor, mutând cele două liste împreună la interschimbare.

Soluție:
n = int(input())
nume = []
punctaje = []
for i in range(n):
    linie = input().split()
    nume.append(linie[0])
    punctaje.append(int(linie[1]))

for i in range(n - 1):
    p = i
    for j in range(i + 1, n):
        if punctaje[j] > punctaje[p]:
            p = j
    punctaje[i], punctaje[p] = punctaje[p], punctaje[i]
    nume[i], nume[p] = nume[p], nume[i]

for i in range(n):
    print(nume[i], punctaje[i])

Verifică: perechea (nume, punctaj) rămâne asociată pentru că interschimbăm ambele liste în același timp.

Scrie pe caiet - De reținut

Titlul lecției

Sortarea în probleme practice - aplicații

Definiția lecției

Sortarea rezolvă probleme reale: construirea clasamentului unui concurs, ordonarea cererilor după coduri sau a punctajelor de la o evaluare. Un clasament se obține sortând descrescător: la fiecare pas căutăm maximul din partea nesortată, cu comparația inversată v[j] > v[p]. Codurile de tip text se ordonează lexicografic, adică alfabetic, cu aceeași selecție a minimului, comparând șirurile caracter cu caracter. La problemele practice alegem metoda după tipul datelor: note într-un interval mic - lista de frecvențe; valori mari sau texte - selecția minimului sau metoda bulelor. De exemplu, pentru punctajele 42 78 55 78 90, clasamentul este 90 78 78 55 42.

Definiții esențiale

Algoritmul cheie - pseudocod

citește n citește punctaje[1..n] pentru i = 1, n - 1 execută p = i pentru j = i + 1, n execută dacă punctaje[j] > punctaje[p] atunci p = j punctaje[i] <-> punctaje[p] scrie punctaje[1..n]

Algoritmul cheie - cod Python

Python - clasamentul concursului
n = int(input())
punctaje = list(map(int, input().split()))

for i in range(n - 1):
    p = i
    for j in range(i + 1, n):
        if punctaje[j] > punctaje[p]:
            p = j
    punctaje[i], punctaje[p] = punctaje[p], punctaje[i]

for x in punctaje:
    print(x, end=" ")

Greșeli comune de evitat

Sfaturi practice și trucuri

Exemplu practic

Un organizator de concurs vrea clasamentul participanților, cu punctajele în ordine descrescătoare. Pentru punctajele 42 78 55 78 90 programul afișează:

Python - clasamentul concursului
punctaje = [42, 78, 55, 78, 90]
n = len(punctaje)

for i in range(n - 1):
    p = i
    for j in range(i + 1, n):
        if punctaje[j] > punctaje[p]:
            p = j
    punctaje[i], punctaje[p] = punctaje[p], punctaje[i]

for x in punctaje:
    print(x, end=" ")

Verifică: se afișează 90 78 78 55 42 - punctajele egale rămân împreună.