Sortarea și căutarea

Cele trei linii, mereu în această ordine:

int t = a[j];
a[j] = a[j + 1];
a[j + 1] = t;

După trecerea i, poziția n - 1 - i este DEFINITIVĂ: maximul zonei a bulat la coadă. De aceea bucla interioară se oprește la n - 1 - i - nu re-verifici ce este deja pe loc.

Candidat + scanare + o singură interschimbare pe trecere:

for (int i = 0; i < n - 1; i++) {
    int poz = i;
    for (int j = i + 1; j < n; j++) {
        if (a[j] < a[poz]) {
            poz = j;
        }
    }
    // interschimba a[i] cu a[poz]
}

La METODA BULELOR, vecinii se interschimbă de câte ori este nevoie (multe swap-uri pe trecere); la SELECȚIE, cauți minimul zonei și faci O SINGURĂ interschimbare pe trecere. Confuzia clasică: scrii a[j] > a[j + 1] (bule) când vroiai a[j] < a[poz] (selecție).

Sentinela -1, zona [st, dr], trei ramuri:

int st = 0;
int dr = n - 1;
int poz = -1;
while (st <= dr && poz == -1) {
    int mij = (st + dr) / 2;
    if (a[mij] == x) {
        poz = mij;
    } else if (x < a[mij]) {
        dr = mij - 1;
    } else {
        st = mij + 1;
    }
}

Pe vector nesortat, decizia „stânga sau dreapta” nu mai spune nimic - răspunsul poate fi greșit fără nicio eroare. Sortează întâi sau folosește căutarea liniară. Și actualizările sunt st = mij + 1, dr = mij - 1: fără +1 și -1, bucla nu se oprește.

Numeri aparițiile fiecărei valori, apoi rescrii valorile în ordine crescătoare:

int f[10] = {0};
for (int i = 0; i < n; i++) {
    f[a[i]]++;
}
for (int v = 0; v <= 9; v++) {
    for (int c = 1; c <= f[v]; c++) {
        cout << v << " ";
    }
}

Indicele din f este o VALOARE, nu o poziție. Vectorul de intrare se parcurge o singură dată.

Numărarea funcționează doar dacă valorile pot fi INDICI în tabloul f: numere întregi, nenegative și mici. Pentru valori mari sau negative, f ar fi imposibil de alocat, iar f[-3] nici nu există - acolo folosești bulele, selecția sau inserția.

A doua capcană: f trebuie pus pe zero ÎNAINTE de numărare. Un tablou local neinițializat conține gunoi, iar contorul pornește de la o valoare aleatoare.

Merge pe ORICE vector, sortat sau nu; -1 înseamnă „nu am găsit”:

int poz = -1;
for (int i = 0; i < n; i++) {
    if (a[i] == x && poz == -1) {
        poz = i;
    }
}

Fără condiția poz == -1, fiecare potrivire suprascrie rezultatul, deci obții ULTIMA apariție. Bug-ul se ascunde bine: pe vectori fără valori repetate cele două variante dau exact același răspuns.

Alegerea între cele două căutări: secvențială pe vector nesortat sau pentru o singură căutare; binară doar pe vector sortat, dar cu mult mai puțini pași.

Salvezi, împingi, cobori - mereu în această ordine:

int x = a[i];
int j = i - 1;
while (j >= 0 && a[j] > x) {
    a[j + 1] = a[j];
    j--;
}
a[j + 1] = x;

Poziția finală este întotdeauna j + 1, indiferent dacă bucla s-a oprit pe j < 0 sau pe a[j] ≤ x.

a[j + 1] = a[j] cu j = i - 1 scrie chiar în a[i]. De aceea condiția buclei trebuie să compare cu copia x, nu cu a[i]: după prima împingere, a[i] nu mai conține valoarea de inserat.

A doua capcană: împingerea merge dinspre coadă spre cap. Dacă parcurgi prefixul crescător și scrii a[j] = a[j + 1], suprascrii fiecare celulă înainte să o copiezi și vectorul se umple cu o singură valoare.