Pe scurt
Această lecție prezintă trei categorii fundamentale de algoritmi: sortarea, căutarea și interclasarea. Sortarea aranjează elementele unui vector într-o ordine specificată, căutarea identifică prezența unui element într-o mulțime de date, iar interclasarea combină doi vectori sortați menținând ordinea. Înțelegerea acestor algoritmi, inclusiv a complexității și stabilității lor, este esențială pentru pregătirea Bacalaureatului la Informatică.
Sortarea – aranjarea elementelor unui șir
Sortarea presupune aranjarea elementelor unui șir (vector) într-o ordine specificată, de obicei crescătoare sau descrescătoare. Cei mai importanți algoritmi de sortare studiați la liceu sunt:
- Bubble Sort (sortare prin metoda bulelor) – complexitate O(n²)
- Selection Sort (sortare prin selecție) – O(n²)
- Insertion Sort (sortare prin inserție) – O(n²) în cazul mediu
- Quick Sort (sortare rapidă) – O(n log n) în cazul mediu, dar O(n²) în cel mai rău caz
- Merge Sort (sortare prin interclasare) – O(n log n) și este stabil
Exemplu – Sortare prin metoda bulelor (Bubble Sort):
Se dă vectorul [5, 3, 8, 4, 2]. Se parcurge vectorul de la stânga la dreapta, comparând perechi adiacente și interschimbându-le dacă nu sunt în ordine crescătoare. După prima parcurgere, cel mai mare element (8) ajunge la final. Se repetă procesul fără ultimul element. Algoritmul se oprește când nu mai are loc nicio interschimbare într-o parcurgere. Etape:
- (5,3,8,4,2) -> (3,5,4,2,8)
- (3,5,4,2,8) -> (3,4,2,5,8)
- (3,4,2,5,8) -> (3,2,4,5,8)
- (3,2,4,5,8) -> (2,3,4,5,8)
Căutarea – găsirea unui element într-o mulțime de date
Căutarea se referă la găsirea unui element într-o mulțime de date. Există două metode principale:
- Căutarea secvențială – simplă, dar ineficientă pentru date mari (O(n))
- Căutarea binară – aplicabilă doar pe date sortate, reduce complexitatea la O(log n) și este esențială pentru înțelegerea tehnicilor divide et impera
Exemplu – Căutare binară:
Se dă vectorul sortat crescător [1, 3, 5, 7, 9, 11]. Căutăm elementul 7.
- Se stabilește stânga=0, dreapta=5. Mijloc = (0+5)/2 = 2 (elementul 5). 5 < 7, deci căutăm în dreapta: stânga=3, dreapta=5.
- Mijloc = (3+5)/2 = 4 (elementul 9). 9 > 7, deci căutăm în stânga: stânga=3, dreapta=3.
- Mijloc =3 (elementul 7). Găsit. Dacă am fi căutat 8, algoritmul ar fi raportat că elementul nu există.
Interclasarea – combinarea a doi vectori sortați
Interclasarea (merge) este procesul de combinare a doi vectori sortați într-unul singur, menținând ordinea. Algoritmul de interclasare are complexitate O(n+m) și este folosit în implementarea Merge Sort.
Exemplu – Interclasare a doi vectori sortați:
Vectorul A = [2, 5, 9], B = [3, 7, 11].
- Se compară primele elemente: 2 < 3, se adaugă 2 în vectorul rezultat.
- Apoi 5 > 3, se adaugă 3.
- Apoi 5 < 7, adaugă 5.
- Apoi 9 > 7, adaugă 7.
- Apoi 9 < 11, adaugă 9.
- Rămâne 11. Rezultat final: [2, 3, 5, 7, 9, 11]. Algoritmul parcurge fiecare vector o singură dată, deci complexitate liniară.
Concepte cheie și aplicații
La Bacalaureat, elevii trebuie să cunoască implementări în pseudocod sau limbaj C/C++ (de obicei C++), să poată analiza complexități și să recunoască situațiile în care se aplică fiecare algoritm. Recomand exersarea pe vectori cu valori întregi, caractere sau obiecte (structuri).
Un alt aspect important este stabilitatea algoritmilor: un algoritm stabil păstrează ordinea relativă a elementelor cu aceeași cheie, ceea ce poate fi decisiv în aplicații complexe (de exemplu, sortarea după mai multe criterii). Exemple: Merge Sort este stabil, Quick Sort este instabil.
În lecțiile noastre, vom urmări să înțelegem nu doar codul, ci și raționamentul matematic din spatele fiecărui algoritm. În final, elevii trebuie să fie capabili să aleagă cel mai potrivit algoritm în funcție de dimensiunea datelor și de constrângerile de timp și memorie.
Concepte cheie
- Sortare: Bubble Sort, Selection Sort, Insertion Sort, Quick Sort, Merge Sort
- Căutare secvențială (O(n)) vs. căutare binară (O(log n)) – necesită date sortate
- Interclasarea a doi vectori sortați – complexitate liniară, utilizată în Merge Sort
- Stabilitatea algoritmilor de sortare (Merge Sort stabil, Quick Sort instabil)
- Analiza complexității (timp și spațiu) în cazul favorabil, mediu și defavorabil
- Tehnica Divide et Impera (Quick Sort, Merge Sort, căutare binară)
Verifică-te!
- Care este complexitatea în cazul mediu a algoritmului Quick Sort și care este complexitatea în cel mai rău caz?
- De ce condiție este necesară pentru a putea aplica căutarea binară pe un vector?
- Ce înseamnă ca un algoritm de sortare să fie stabil și care dintre algoritmii prezentați este stabil?