Explică-mi mai detaliat: Algoritmi fundamentali (sortare, cautare, interclasare)

🔍 Algoritmi Fundamentali: Sortare, Căutare, Interclasare

Salut! Hai să aprofundăm împreună acești algoritmi esențiali pentru Bacalaureat. Îți voi explica fiecare algoritm pas cu pas, cu exemple concrete și cod în C++.

• --

1. Sortarea (Algoritmi de ordonare)

Ce înseamnă sortarea?

Sortarea = aranjarea elementelor unui vector într-o anumită ordine (crescătoare sau descrescătoare).

📊 Comparația algoritmilor de sortare

| Algoritm | Complexitate (caz mediu) | Complexitate (caz defavorabil) | Memorie suplimentară |

|----------|--------------------------|-------------------------------|---------------------|

| Bubble Sort | O(n²) | O(n²) | O(1) |

| Selection Sort | O(n²) | O(n²) | O(1) |

| Insertion Sort | O(n²) | O(n²) | O(1) |

| Merge Sort | O(n log n) | O(n log n) | O(n) |

| Quick Sort | O(n log n) | O(n²) | O(log n) |

• --

🔵 Bubble Sort (Sortare prin metoda bulelor)

Ideea algoritmului:

• Comparăm elemente adiacente

• Dacă sunt în ordine greșită, le interschimbăm

• La fiecare parcurgere, cel mai mare element "plutește" la final (ca o bulă)

Pseudocod:

Implementare C++:

Exemplu vizual:

• --

🟢 Selection Sort (Sortare prin selecție)

Ideea algoritmului:

• Găsim minimul din partea nesortată

• Îl plasăm la începutul părții nesortate

• Repetăm până când tot vectorul e sortat

Pseudocod:

Implementare C++:

Exemplu: Pentru v = [5, 2, 8, 1, 9]:

• Pasul 1: minimul din [5,2,8,1,9] e 1 → [1, 2, 8, 5, 9]

• Pasul 2: minimul din [2,8,5,9] e 2 → deja la locul lui

• Pasul 3: minimul din [8,5,9] e 5 → [1, 2, 5, 8, 9]

• Pasul 4: minimul din [8,9] e 8 → deja la locul lui

• Rezultat: [1, 2, 5, 8, 9] ✓

• --

🟡 Insertion Sort (Sortare prin inserare)

Ideea algoritmului:

• Construim treptat un subșir sortat

• Fiecare element nou e inserat în poziția corectă

• E eficient pentru șiruri aproape sortate

Pseudocod:

Implementare C++:

• --

🔴 Merge Sort (Sortare prin interclasare) - O(n log n)

Ideea algoritmului:

• Divide: împărțim vectorul în două jumătăți

• Conquer: sortăm recursiv fiecare jumătate

• Combine: interclasăm cele două jumătăți sortate

Implementare C++:

• --

2. Căutarea (Algoritmi de căutare)

📗 Căutarea Liniară (Secvențială)

Ideea algoritmului:

• Parcurgem vectorul de la început

• Verificăm fiecare element dacă e egal cu valoarea căutată

• Complexitate: O(n)

Implementare C++:

• --

📘 Căutarea Binară - O(log n)

Condiție obligatorie: Vectorul trebuie să fie SORTAT!

Ideea algoritmului:

• Împărțim repetat intervalul de căutare în jumătăți

• Comparăm elementul din mijloc cu valoarea căutată

• Eliminăm jumătatea care nu poate conține valoarea

Pseudocod:

Implementare C++:

Exemplu vizual:

• --

3. Interclasarea (Merge)

Ce este interclasarea?

Interclasarea combină doi vectori deja sortați într-un singur vector sortat.

Complexitate: O(n + m), unde n și m sunt lungimile vectorilor.

Algoritmul de interclasare

Ideea algoritmului:

• Comparăm primul element din fiecare vector

• Luăm cel mai mic și îl adăugăm în vectorul rezultat

• Avansăm în vectorul din care am luat elementul

• Repetăm până epuizăm un vector

• Adăugăm restul elementelor din vectorul rămas

Pseudocod:

Implementare C++:

Exemplu: A = [1, 4, 7], B = [2, 3, 8]

• Comparăm 1 și 2 → luăm 1 → C = [1]

• Comparăm 4 și 2 → luăm 2 → C = [1, 2]

• Comparăm 4 și 3 → luăm 3 → C = [1, 2, 3]

• Comparăm 4 și 8 → luăm 4 → C = [1, 2, 3, 4]

• Comparăm 7 și 8 → luăm 7 → C = [1, 2, 3, 4, 7]

• B mai are 8 → C = [1, 2, 3, 4, 7, 8] ✓

• --

🎯 Aplicații în probleme de Bacalaureat

Problema tipică 1: Sortare + Căutare

Cerință: Se citește un vector, se sortează și se verifică dacă un element x se află în vector.

Strategie:

1. Sortăm vectorul (Selection Sort pentru simplitate)

2. Folosim căutarea binară (cum vectorul e sortat)

Problema tipică 2: Interclasare a doi vectori

Cerință: Se citesc doi vectori sortați, se cere interclasarea lor.

Strategie:

1. Aplicăm direct algoritmul de interclasare

2. Atenție la cazurile când un vector se epuizează

Problema tipică 3: Eliminarea duplicatelor

Cerință: Se citește un vector nesortat, se cere eliminarea elementelor duplicate.

Strategie:

1. Sortăm vectorul

2. Parcurgem și păstrăm doar elementele diferite de precedentul

• --

📝 Verifică-te!

Exercițiul 1

Scrie un program care citește un vector cu n elemente și verifică dacă conține valoarea x, folosind căutarea binară.

Indiciu: Mai întâi sortează vectorul, apoi aplică căutarea binară. Testează cu vectorul [5, 2, 8, 1, 9] și x = 8.

Exercițiul 2

Scrie un program care citește doi vectori sortați și afișează interclasarea lor.

Indiciu: Folosește exact algoritmul de interclasare prezentat mai sus. Testează cu A = [1, 3, 5, 7] și B = [2, 4, 6, 8, 10].

• --

💡 Sfaturi pentru Bacalaureat

1. Memorează complexitățile: O(n²) pentru sortările simple, O(n log n) pentru Merge Sort, O(log n) pentru căutarea binară

2. Recunoaște tiparele: "Se cere sortare" → alege algoritmul potrivit; "Vector sortat