Sortare si cautare

Sortare prin selectie

La fiecare pas, gaseste minimul din subsirul nesortat si il pune pe pozitia corecta.

Complexitate: O(n²)

for (int i = 1; i <= n - 1; i++) {
    int imin = i;
    for (int j = i + 1; j <= n; j++)
        if (v[j] < v[imin]) imin = j;
    swap(v[i], v[imin]);
}

---

Sortare prin insertie

Insereaza fiecare element in pozitia corecta in subblocul deja sortat.

Complexitate: O(n²) — eficienta pe date aproape sortate

for (int i = 2; i <= n; i++) {
    int key = v[i], j = i - 1;
    while (j >= 1 && v[j] > key) {
        v[j + 1] = v[j];
        j--;
    }
    v[j + 1] = key;
}

---

Sortare prin interclasare (Merge Sort)

Divide vectorul in doua jumatati, le sorteaza recursiv, le interclaseaza.

Complexitate: O(n log n)

void mergeSort(int v[], int st, int dr) {
    if (st >= dr) return;
    int mij = (st + dr) / 2;
    mergeSort(v, st, mij);
    mergeSort(v, mij + 1, dr);
    // interclasare
    int temp[100001], k = st, i = st, j = mij + 1;
    while (i <= mij && j <= dr)
        temp[k++] = (v[i] <= v[j]) ? v[i++] : v[j++];
    while (i <= mij) temp[k++] = v[i++];
    while (j <= dr)  temp[k++] = v[j++];
    for (int x = st; x <= dr; x++) v[x] = temp[x];
}

---

Sortare cu sort() din STL

#include <algorithm>
sort(v + 1, v + n + 1);           // crescator
sort(v + 1, v + n + 1, greater<int>());  // descrescator

La BAC, sort() e permis. Cunoaste si un algoritm manual.

---

Cautare secventiala (liniara)

Parcurge elementele unu cate unu. Functioneaza pe orice vector.

Complexitate: O(n)

int cautare(int v[], int n, int x) {
    for (int i = 1; i <= n; i++)
        if (v[i] == x) return i;
    return -1;  // negasit
}

---

Cautare binara

Functioneaza doar pe vector sortat. Injumatateste spatiul la fiecare pas.

Complexitate: O(log n)

int cautareBinara(int v[], int n, int x) {
    int st = 1, dr = n;
    while (st <= dr) {
        int mij = (st + dr) / 2;
        if (v[mij] == x) return mij;
        else if (v[mij] < x) st = mij + 1;
        else dr = mij - 1;
    }
    return -1;  // negasit
}

---

Interclasarea a doi vectori sortati

// a[1..n] si b[1..m] sortati → c[1..n+m] sortat
int i = 1, j = 1, k = 0;
while (i <= n && j <= m)
    c[++k] = (a[i] <= b[j]) ? a[i++] : b[j++];
while (i <= n) c[++k] = a[i++];
while (j <= m) c[++k] = b[j++];

---

La examen

• Sortare selectie: cel mai usor de scris manual, cere-l daca nu stii altceva
• Cautare binara: conditie obligatorie — vectorul trebuie sortat
• La cautare binara traseaza: st, dr, mij la fiecare iteratie
• sort() din STL e O(n log n) si e suficient in cele mai multe subiecte