Metode de ordonare: bule, selecție, inserție, numărare

Pe scurt

1 minesențialul, de recitit oricând

Culorile din lecție:termencifră, datăidee-cheie

• Programa numește patru metode: bule, selecție, inserție, numărare. Sunt pentru ambele specializări.
• În lucrările C/C++ importate (2020–2027) niciuna nu e numită. Nu se cere „aplică metoda bulelor”. Ordonarea apare în secvențe scurte, iar baremul acceptă orice algoritm principial corect.
• Învață bine una dintre metodele cu comparații și metoda numărării: pe a doua o vei folosi la III.3, sub numele de vector de frecvență.

Urmează · 1 min

Ce se cere, de fapt

4 min

Am căutat în cele 67 de lucrări și în baremele lor (2020–2027, C/C++) cuvintele bule, inserție, selecție, numărare, sortare. Niciunul nu apare ca nume de metodă. Totuși programa le cere, iar o lucrare viitoare le-ar putea numi, așa că le găsești mai jos pe toate patru.

Urmează · 4 min

Metoda bulelor

2 min o întrebare la final

Mergi prin șir și compari fiecare pereche de vecini. Dacă sunt în ordine greșită, îi schimbi. Valoarea mare ajunge spre capăt, ca o bulă care urcă. Repeți până când o parcurgere nu mai schimbă nimic.

do
{ ok=1;
  for(i=0;i<n-1;i++)
    if(a[i]>a[i+1])
    { aux=a[i];
      a[i]=a[i+1];
      a[i+1]=aux;
      ok=0;
    }
}while(ok==0);

Urmează · 2 min

Metoda selecției

2 min

Pentru fiecare poziție i, cauți minimul de la i până la capăt și îl aduci pe poziția i.

for(i=0;i<n-1;i++)
{ p=i;
  for(j=i+1;j<n;j++)
    if(a[j]<a[p]) p=j;
  aux=a[i];
  a[i]=a[p];
  a[p]=aux;
}

Selecția folosește același algoritm de minim cu poziție ca la tablouri. Dacă îl știi pe acela, o scrii ușor.

Urmează · 2 min

Metoda inserției

2 min

Ca la cărțile de joc: partea din stânga e deja în ordine. Iei valoarea următoare, muți cu o poziție spre dreapta tot ce e mai mare și o pui în locul rămas liber.

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

Urmează · 2 min

Metoda numărării

5 min 2 întrebări la final

Dacă valorile sunt dintr-un interval mic, nu e nevoie să le compari. Numeri câte sunt din fiecare, apoi le scrii în ordine.

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

Pentru (5,2,9,1): f[1], f[2], f[5], f[9] sunt 1, restul 0. Se afișează 1 2 5 9.

Oficial, f se numește vector de frecvență. Baremele îl propun ca soluție la III.3. De exemplu, la model 2027 baremul spune că „o soluție posibilă utilizează” un astfel de vector, cu punctajul total pentru fiecare echipă. Iar la iunie 2020, varianta 6, descrie un vector cu „numărul de apariții ale lui x”. E aceeași idee: indicele e o valoare, iar elementul e ce știi despre ea.

În Pascal se schimbă doar forma tablourilor și a structurilor (for i:=0 to n-2 do, repeat ... until), nu logica.

Urmează · 5 min

Oficial: august 2020, varianta 5, MI, II.3

4 min

Variabila a e un tablou bidimensional cu 6 linii și 4 coloane, numerotate de la 0. Se cere o secvență care rearanjează elementele pare de pe coloana a 3-a, în ordine crescătoare de sus în jos, iar celelalte elemente rămân pe loc. Variabilele i, j, k sunt deja declarate.

În exemplul oficial se schimbă coloana cu indicele 2: 4 8 5 2 1 0 devine 0 2 5 4 1 8. Deci „a 3-a” înseamnă a treia la număr. Când textul lasă loc de interpretare, exemplul decide.

for(i=0;i<5;i++)
  if(a[i][2]%2==0)
    for(j=i+1;j<6;j++)
      if(a[j][2]%2==0)
        if(a[j][2]<a[i][2])
        { k=a[i][2];
          a[i][2]=a[j][2];
          a[j][2]=k;
        }

Interschimbi doar perechi în care ambele valori sunt pare, așa că valorile impare nu se mișcă.

Urmează · 4 min

Oficial: model 2023, SN, II.2

3 min

Pentru trei echipe, i1, i2, i3 memorează indicativele (litere), iar r1, r2, r3 rezultatele, distincte. Se declară variabilele și se afișează indicativele, în ordinea descrescătoare a rezultatelor.

Trei valori se ordonează cu trei comparații: e metoda bulelor, scrisă pe scurt. Odată cu rezultatele trebuie să muți și indicativele.

char i1,i2,i3,c;
int r1,r2,r3,aux;
// valorile sunt deja memorate
if(r1<r2)
{ aux=r1; r1=r2; r2=aux;
  c=i1; i1=i2; i2=c;
}
if(r2<r3)
{ aux=r2; r2=r3; r3=aux;
  c=i2; i2=i3; i3=c;
}
if(r1<r2)
{ aux=r1; r1=r2; r2=aux;
  c=i1; i1=i2; i2=c;
}
cout<<i1<<" "<<i2<<" "<<i3;

Barem: identificarea valorilor în ordinea cerută 4 p, câte 2 p pentru algoritmul de ordonare sau identificare principial corect și pentru criteriul de ordonare; afișare 1 p; corectitudine globală 1 p. Se acceptă și o rezolvare fără interschimbări, cu if pentru fiecare ordine posibilă. La matematică-informatică, cerința e aceeași, cu un tablou de trei înregistrări, struct echipa c[3].

Urmează · 3 min

Ce se cere la BAC

1 mincum apare la examen

• La secvențe de 6 p, alege metoda pe care o scrii fără greșeli. Baremul nu cere un nume.
• La III.3, o ordonare a tuturor valorilor cu două bucle nu e liniară, deci nu ia punctul de eficiență. Caută soluția cu vector de frecvență sau cu câteva variabile.
• Dacă datele sunt deja ordonate, cum e la simulare 2026, III.3, nu le mai ordona. Vezi lecția despre căutare și complexitate.

Urmează · 1 min

Greșeli care costă puncte

1 mincapcanele de evitat

• O singură parcurgere la bule, fără repetare.
• i<n cu a[i+1]: accesezi un element în afara șirului.
• p neinițializat la selecție pentru fiecare i nou.
• a[j+1]=x uitat la inserție, după ce ai mutat valorile.
• Date care nu se mișcă împreună: la model 2023, dacă schimbi rezultatele, schimbă și indicativele.
• Vector de frecvență dimensionat după numărul de valori, nu după cea mai mare valoare.

Urmează · 1 min