Sortare prin selecție și bule la BAC: pași și C++

Sortarea prin selecție și sortarea prin metoda bulelor ordonează un vector prin comparații și schimburi, dar fixează elementele în moduri diferite. Selecția caută cel mai mic element din partea neordonată și îl pune la începutul ei. Metoda bulelor compară vecini și împinge treptat valorile mari spre final.

La BAC, este important să recunoști ce parte a vectorului devine definitiv ordonată după o etapă. Această observație explică limitele buclelor și ajută la urmărirea programului pe hârtie. Vom folosi ordine crescătoare, cu egalități permise, și exemple potrivite pentru antrenamentul pe subiecte BAC.

Ce înseamnă că un vector este ordonat crescător

În sensul folosit aici, fiecare element este mai mic sau egal cu următorul. Vectorul unu, trei, trei, opt este ordonat crescător, chiar dacă două valori vecine sunt egale. Dacă enunțul cere ordine strict crescătoare, egalitățile nu mai sunt permise.

Sortarea schimbă ordinea, dar trebuie să păstreze exact valorile și numărul aparițiilor lor. Dacă intrarea conține două valori trei, rezultatul trebuie să le conțină pe ambele. Eliminarea duplicatelor este o altă operație.

O verificare completă urmărește deci două proprietăți: ordinea corectă și păstrarea elementelor. Un vector care arată ordonat, dar a pierdut o valoare în urma unui schimb greșit, nu este rezultatul corect al sortării.

Selecția minimului din partea rămasă

Pornim cu vectorul șase, trei, cinci, unu. La prima etapă căutăm minimul întregului vector. Este unu, aflat la final. Îl schimbăm cu primul element, obținând unu, trei, cinci, șase.

La a doua etapă căutăm minimul numai de la a doua poziție încolo. Acesta este trei, deja la locul potrivit. Următoarea etapă fixează cinci, iar ultimul element rămâne automat corect după fixarea tuturor celor anterioare.

Etapă	Partea în care căutăm minimul	Prefix fixat după etapă
Prima	Întregul vector	1
A doua	De la al doilea element la final	1, 3
A treia	Ultimele două elemente	1, 3, 5

Prefixul fixat nu mai trebuie modificat. El conține cele mai mici valori în ordinea corectă. Această semnificație justifică de ce căutarea minimului începe tot mai la dreapta.

Program C++ pentru selecție

Programul citește între zero și o mie de numere întregi și le afișează ordonate crescător. Variabila pentru poziția minimului este reinițializată la fiecare etapă, deoarece căutăm într-o altă parte a vectorului.

#include <iostream>
using namespace std;

int main() {
    int n, v[1000];
    cin >> n;
    for (int i = 0; i < n; ++i) cin >> v[i];
    for (int i = 0; i < n - 1; ++i) {
        int p = i;
        for (int j = i + 1; j < n; ++j)
            if (v[j] < v[p]) p = j;
        if (p != i) {
            int aux = v[i];
            v[i] = v[p];
            v[p] = aux;
        }
    }
    for (int i = 0; i < n; ++i) {
        if (i > 0) cout << ' ';
        cout << v[i];
    }
    return 0;
}

Schimbul folosește o variabilă auxiliară pentru a păstra valoarea primei celule. Dacă ai atribui direct valoarea celei de-a doua peste prima și apoi ai copia prima în a doua, ambele celule ar putea ajunge egale. Ai pierde una dintre valorile inițiale.

Pentru zero sau un singur element, bucla de sortare nu se execută. Rezultatul este deja ordonat. Limitele semnate din program permit evaluarea corectă a condiției și pentru lungimea zero.

Metoda bulelor și comparația vecinilor

Într-o trecere de la stânga spre dreapta, compari fiecare pereche de vecini și faci schimb dacă elementul din stânga este mai mare. După această trecere, cel mai mare element din zona parcursă ajunge la capătul din dreapta.

Pentru patru, doi, trei, unu, prima comparație produce doi, patru, trei, unu. Următoarea produce doi, trei, patru, unu. Ultima produce doi, trei, unu, patru. Maximul patru este acum fixat, dar restul vectorului nu este încă ordonat.

A doua trecere poate ignora ultimul element. După următoarele comparații obții doi, unu, trei, patru, iar a treia trecere produce unu, doi, trei, patru. În această direcție a parcurgerii, se fixează un sufix, nu un prefix.

Oprirea când nu mai există schimburi

La începutul fiecărei treceri poți presupune că nu vei face niciun schimb. Dacă apare o pereche în ordine greșită, o schimbi și marchezi faptul că trecerea a modificat vectorul. Dacă întreaga trecere se încheie fără schimburi, vectorul este ordonat.

Această optimizare ajută când datele sunt deja ordonate sau devin ordonate înaintea numărului maxim de treceri. Indicatorul trebuie însă resetat la fiecare trecere. Dacă păstrezi pentru totdeauna informația că a existat cândva un schimb, condiția de oprire nu mai descrie trecerea curentă.

Comparația pentru schimb trebuie să fie strictă. Dacă schimbi și elementele egale și folosești numai absența schimburilor ca oprire, egalitățile pot provoca treceri inutile sau chiar împiedica oprirea unei implementări greșite.

Câte comparații fac metodele

Selecția din program compară un număr fix de perechi pentru o lungime dată: la prima etapă compară cu toate elementele rămase, apoi cu unul mai puțin și tot așa. Totalul este jumătate din produsul dintre lungime și lungimea micșorată cu unu.

Prin urmare, timpul este pătratic în lungime, inclusiv când vectorul era deja ordonat. Numărul schimburilor efective poate fi mic, dar comparațiile sunt în continuare executate. Nu confunda aceste două tipuri de operații.

Metoda bulelor are și ea timp pătratic în cazul nefavorabil. Cu oprire după o trecere fără schimburi, un vector deja ordonat poate fi verificat într-un timp liniar. Pentru date foarte multe, trebuie analizat dacă limitele problemei permit o metodă pătratică.

Stabilitatea și elementele egale

O sortare este stabilă dacă păstrează ordinea relativă a elementelor cu aceeași cheie. Pentru numere simple egale, diferența nu se vede. Devine importantă când fiecare număr este asociat cu un nume, o poziție inițială sau alte date.

Selecția cu schimburi la distanță din program nu este în general stabilă. Metoda bulelor care schimbă numai vecinii aflați în ordine strict greșită este stabilă. Elementele egale nu se depășesc unul pe altul prin asemenea schimburi.

De exemplu, marchează două valori doi drept doi-A și doi-B, păstrând cheia numerică doi. În secvența doi-A, doi-B, unu, selecția minimului poate produce unu, doi-B, doi-A. Valorile sunt ordonate, dar ordinea celor două etichete s-a inversat.

Exerciții cu verificare

După prima etapă de selecție pentru opt, patru, șase, doi, rezultatul este doi, patru, șase, opt. Elementul doi este fixat. Restul este întâmplător ordonat, dar algoritmul general continuă verificările.

După prima trecere a bulelor pentru trei, unu, doi, rezultatul este unu, doi, trei. Maximul trei a ajuns la final prin două comparații. Nu presupune că prima trecere sortează orice vector.

Pentru cinci elemente, câte comparații face selecția prezentată? Zece: patru, apoi trei, apoi două, apoi una. Numărul nu depinde de valorile concrete.

Cum obții ordine descrescătoare? Schimbi sensul comparațiilor care aleg extrema sau decid schimbul. Justifică apoi ce prefix ori sufix este fixat, pentru a păstra înțelegerea pașilor.

Întrebări frecvente

Sortarea elimină valorile repetate?

Nu. Ea păstrează toate aparițiile și le schimbă doar ordinea. Eliminarea duplicatelor trebuie cerută și implementată separat.

Pot opri selecția când nu am făcut un schimb?

Nu după o singură etapă fără schimb. Minimul zonei curente poate fi deja pe prima poziție, în timp ce partea rămasă este încă neordonată. Oprirea bulelor se bazează pe o trecere completă fără schimburi.

Cum verific o simulare pe foaie?

Marchează partea deja fixată și notează fiecare schimb real. Testează valori egale și un vector invers ordonat. Pentru corectarea unei simulări, poți lucra punctual la meditații de informatică.