Algoritmi fundamentali (sortare, cautare, interclasare)

Pe scurt

Algoritmii fundamentali (sortare, căutare, interclasare) reprezintă baza programării și a gândirii algoritmice, fiind esențiali pentru pregătirea Bacalaureatului la Informatică. Sortarea aranjează elementele unui șir într-o ordine specifică, căutarea găsește un element într-o structură de date, iar interclasarea combină două șiruri sortate într-unul singur. Elevii trebuie să înțeleagă diferențele de complexitate și să poată implementa corect acești algoritmi în limbajul C++ (sau Pascal).

Algoritmi de sortare

Sortarea este procesul de aranjare a elementelor unui șir într-o ordine specifică (crescătoare sau descrescătoare). Cei mai importanți algoritmi de sortare sunt:

• Bubble Sort (sortare prin bule) – complexitate O(n²), care compară și interschimbă elemente adiacente până la ordonare
• Selection Sort (sortare prin selecție) – O(n²), care la fiecare pas alege minimul din porțiunea nesortată și îl plasează la început
• Insertion Sort (sortare prin inserare) – O(n²), dar eficient pentru șiruri aproape sortate, prin inserarea fiecărui element în poziția corectă dintr-o subsecvență deja sortată
• Quick Sort (sortare rapidă) – O(n²) în cazul cel mai defavorabil, dar O(n log n) în medie, folosind partiționarea

Pentru Bac se cer cunoașterea și implementarea algoritmilor elementari, precum și analiza eficienței.

Exemplu – Sortare prin selecție (Selection Sort): Fie vectorul v = [5, 2, 8, 1, 9]. Se parcurge vectorul: la pasul 1, găsim minimul (1) și îl interschimbăm cu primul element: [1, 2, 8, 5, 9]. Pasul 2 – minimul din [2,8,5,9] este 2, deja la locul lui. Pasul 3 – minimul din [8,5,9] este 5, se interschimbă cu 8: [1,2,5,8,9]. Pasul 4 – minimul din [8,9] este 8. Rezultat final: [1,2,5,8,9].

Algoritmi de căutare

Căutarea este procesul de găsire a unui element într-o structură de date.

• Căutarea liniară – parcurge secvențial elementele, având complexitate O(n)
• Căutarea binară – O(log n), se aplică doar pe șiruri sortate, împărțind repetat șirul în jumătăți

Exemplu – Căutare binară: Fie vectorul sortat v = [2, 5, 8, 12, 16, 23, 38] și x=23. Se inițializează stânga=0, dreapta=6. Mijloc = (0+6)/2=3, v[3]=12 < 23, deci stânga=4. Noul mijloc = (4+6)/2=5, v[5]=23 == x, deci s-a găsit pe poziția 5. Complexitate O(log n).

Algoritmul de interclasare

Interclasarea (merge) combină două șiruri sortate într-unul singur, sortat, în O(n+m). Este utilizată în algoritmul Merge Sort și în probleme de unificare a vectorilor. În problemele de Bac, interclasarea apare frecvent la prelucrarea fișierelor și la combinarea a doi vectori ordonați.

Exemplu – Interclasare a doi vectori sortați: A = [1, 4, 7], B = [2, 3, 8]. Se compară primii elemente: 1<2, se adaugă 1. Apoi 4>2, se adaugă 2. Apoi 4>3, se adaugă 3. Apoi 4<8, se adaugă 4. Apoi 7<8, se adaugă 7. Apoi se adaugă ultimul element rămas din B, 8. Rezultat: [1,2,3,4,7,8].

Aplicarea algoritmilor în probleme de Bacalaureat

Elevii trebuie să înțeleagă diferențele de complexitate și să poată implementa corect acești algoritmi în limbajul C++ (sau Pascal). De asemenea, este importantă aplicarea lor în contexte precum sortarea unui vector, căutarea unui element, determinarea frecvențelor, eliminarea duplicatelor etc.

Concepte cheie: Sortare (Bubble, Selection, Insertion, Quick), Căutare liniară și binară, Interclasare a doi vectori sortați, Complexitate temporală O(n), O(n log n), O(n²), Aplicarea algoritmilor în probleme Bacalaureat.

Metoda backtracking și algoritmii greedy sunt tratați separat, dar sortarea, căutarea și interclasarea sunt bazele pe care se construiesc soluții mai avansate. Pentru o pregătire temeinică, se recomandă rezolvarea a cât mai multor probleme de pe site-uri de evaluare (PbInfo, InfoArena) și analiza atentă a cerințelor din variantele de Bac.

Verifică-te!

1. Care este complexitatea temporală a algoritmului Bubble Sort în cazul general?
2. Ce condiție trebuie îndeplinită pentru a putea aplica căutarea binară pe un șir de date?
3. În ce constă principiul de funcționare al interclasării a doi vectori sortați?