SISergiu Ilincameditații informatică
Meniu

clasa a X-a · Tablouri unidimensionale · lecția 4

Sortarea vectorilor: bule, selecție, inserție (și sort din STL)

60 mintoate profilurile

Înainte de lecția asta: X.3 Vectori: ștergeri, inserări și verificarea proprietăților

Ce vei ști după lecție

  • Implementezi metoda bulelor, sortarea prin selecție și prin inserție.
  • Urmărești pas cu pas o sortare (exercițiu frecvent la grile).
  • Sortezi după un criteriu (suma cifrelor, paritate, descrescător).
  • Folosești sort() din biblioteca <algorithm> când e permis.

Lecția are și o fișă de lucru, de rezolvat după ce o citești. Mergi la fișă ↓

Clasa a X-aLecția 4 din 13 · mai sunt 9Urmează: X.5 · Căutarea secvențială, căutarea binară și interclasareaVezi toate lecțiile
Cuprins

Fișiere PDF și de lucru

1. Ideea de sortare

A sorta (ordona) un vector înseamnă a-i rearanja elementele crescător (sau descrescător). Toate metodele simple se bazează pe comparații și interschimbări (swap).

De ce așa?

De ce sortăm? Un vector sortat face multe lucruri ușoare: căutarea binară (lecția următoare), eliminarea duplicatelor, găsirea medianei, perechi apropiate, interclasarea. De multe ori „sortează întâi” transformă o problemă O(n²) într-una O(n log n).

2. Metoda bulelor (Bubble Sort)

Comparăm perechi de elemente vecine și le interschimbăm dacă sunt în ordine greșită. Repetăm până când nu mai facem nicio interschimbare. Elementele mari „urcă” spre final ca bulele într-un pahar cu sifon.

Metoda bulelor

#include <iostream>
#include <algorithm>
using namespace std;

int a[1001], n;

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    bool sortat;
    do
    {
        sortat = true;
        for (int i = 1; i < n; i++)
            if (a[i] > a[i + 1])
            {
                swap(a[i], a[i + 1]);
                sortat = false;
            }
    } while (!sortat);
    for (int i = 1; i <= n; i++)
        cout << a[i] << ' ';
    return 0;
}

Urmărire pe (5, 1, 4, 2):

Trecere Vector după trecere Interschimbări
1 1 4 2 5 3
2 1 2 4 5 1
3 1 2 4 5 0 → stop

De ce așa?

De ce se opresc „bulele” după sortat == true? Dacă o trecere întreagă nu a găsit nicio pereche în ordine greșită, atunci toate perechile vecine sunt în ordine, deci vectorul este sortat. Fără indicatorul sortat ai face mereu n − 1 treceri, chiar și pe un vector deja sortat. După trecerea k, ultimele k elemente sunt pe locul lor definitiv.

3. Sortarea prin selecție (Selection Sort)

Pentru fiecare poziție i, găsim minimul din restul vectorului și îl aducem pe poziția i.

Selecție

for (int i = 1; i < n; i++)
    for (int j = i + 1; j <= n; j++)
        if (a[j] < a[i])
            swap(a[i], a[j]);

(Varianta de mai sus interschimbă la fiecare element mai mic; varianta „clasică” reține poziția minimului și face o singură interschimbare pe pas.)

i j a[j] < a[i]? vector după
1 2 2 < 5 da 2 5 4 1
1 3 4 < 2 nu 2 5 4 1
1 4 1 < 2 da 1 5 4 2
2 3 4 < 5 da 1 4 5 2
2 4 2 < 4 da 1 2 5 4
3 4 4 < 5 da 1 2 4 5

De ce așa?

De ce poziția i primește mereu minimul? Când j termină de parcurs restul, a[i] a fost comparat cu fiecare element din dreapta și a „ținut” cea mai mică valoare întâlnită. Prefixul a[1..i] este definitiv: conține cele mai mici i valori, în ordine.

4. Sortarea prin inserție (Insertion Sort)

Ca la sortarea cărților de joc în mână: luăm pe rând fiecare element și îl inserăm la locul lui în partea deja sortată.

Inserție

#include <iostream>
using namespace std;

int a[1001], n;

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 2; i <= n; i++)
    {
        int x = a[i], j = i - 1;
        while (j >= 1 && a[j] > x)
        {
            a[j + 1] = a[j];     // mutăm spre dreapta
            j--;
        }
        a[j + 1] = x;
    }
    for (int i = 1; i <= n; i++)
        cout << a[i] << ' ';
    return 0;
}

De ce așa?

De ce se salvează x = a[i] înainte? Mutările la dreapta suprascriu a[i] (prima mutare e a[i] = a[i-1]). Fără copie pierdem elementul pe care vrem să-l inserăm. Este aceeași idee ca „paharul gol” de la interschimbare.

5. Comparație

Metodă Comparații (cel mai rău caz) Observație
bule ~n² se oprește devreme dacă vectorul e aproape sortat
selecție ~n²/2 număr fix de comparații, puține interschimbări
inserție ~n²/2 foarte rapidă pe vectori aproape sortați
sort() (STL) ~n log n cea mai rapidă; folosește-o când nu ți se cere explicit metoda

Pentru n = 10⁵: metodele de mână fac ~10¹⁰ operații (zeci de secunde), iar sort ~2·10⁶ (instant).

La BAC

La Bac se acceptă orice metodă de sortare corectă, dar la III.3 (eficiență) o sortare O(n²) pe 10⁶ numere nu mai este eficientă. Deseori problema nu cere sortare deloc: caută o soluție cu vector de frecvență sau „din mers”.

6. Sortarea după un criteriu

Schimbi doar condiția de comparare.

// descrescător
if (a[i] < a[i + 1]) swap(a[i], a[i + 1]);

// crescător după suma cifrelor; la egalitate, crescător după valoare
if (sc(a[i]) > sc(a[i + 1]) || (sc(a[i]) == sc(a[i + 1]) && a[i] > a[i + 1]))
    swap(a[i], a[i + 1]);

(sc = o funcție care calculează suma cifrelor; le învățăm la subprograme. Până atunci poți calcula sumele într-un vector separat și să le interschimbi împreună.)

De ce așa?

De ce funcționează la fel pentru orice criteriu? Algoritmul nu „știe” ce înseamnă „mai mic”: îl întreabă pe if. Orice relație care spune „a trebuie să fie înaintea lui b” e un criteriu valid, cu condiția să fie coerentă (să nu se contrazică).

Sortarea doar a unor elemente

Exemplu: ordonează crescător doar elementele pare, celelalte rămân pe loc. Idee: extragi elementele pare într-un vector auxiliar, îl sortezi, apoi le pui înapoi pe pozițiile elementelor pare, în ordine.

7. sort() din STL

#include <algorithm>
// ...
sort(a + 1, a + n + 1);                    // sortează a[1..n] crescător
sort(a + 1, a + n + 1, greater<int>());    // descrescător

De știut

La exercițiile de pe pbinfo în care scrie explicit „folosind metoda bulelor”, scrie metoda de mână: scopul e să înveți algoritmul. La Bac, folosirea lui sort este acceptată dacă problema nu cere o anumită metodă.

8. Greșeli frecvente

Greșeala Efect Corect
for (i = 1; i <= n; i++) cu a[i+1] citești a[n+1] i < n
interschimbare fără al treilea element ambele ajung egale swap sau aux
sort(a, a + n) pe vector indexat de la 1 sortezi cu a[0] inclus sort(a + 1, a + n + 1)
uiți indicatorul sortat merge, dar mereu lent sortat = false la interschimbare
sortare O(n²) pe 10⁶ elemente timp depășit sort() sau altă idee

9. La BAC

La BAC

În grile apar „care secvență ordonează descrescător tabloul” și „vectorul după prima trecere”. Fă tabel cu starea vectorului după fiecare pas. La Subiectul III cu sortare, alege sort(), dacă enunțul nu impune altceva.

10. Exersează pe hârtie

Răspunsurile sunt la final: încearcă întâi singur.

1. Se aplică metoda bulelor pe (6, 3, 8, 1, 5). Care e vectorul după prima trecere completă?

2. Câte interschimbări face selecția (varianta din secțiunea 3) pe (4, 3, 2, 1)?

3. Ordonează un vector astfel încât elementele pare să fie la început (crescător), iar cele impare la final (descrescător).

4. Câte treceri face metoda bulelor (cu indicator) pe (2, 1, 3, 4, 5)? Câte pe (5, 4, 3, 2, 1)?

5. Ce afișează for (i = 1; i < n; i++) if (a[i] > a[i + 1]) swap(a[i], a[i + 1]); pentru (3, 1, 2) (o singură trecere)?

6. Care dintre secvențele următoare ordonează descrescător vectorul a[1..n]?

a) for (i=1;i<n;i++) for (j=i+1;j<=n;j++) if (a[i]<a[j]) swap(a[i],a[j]);
b) for (i=1;i<n;i++) for (j=i+1;j<=n;j++) if (a[i]>a[j]) swap(a[i],a[j]);
c) sort(a+1, a+n+1);
d) sort(a+1, a+n+1, greater<int>());

7. Care este avantajul sortării prin inserție față de bule pe un vector aproape sortat?

11. Mai departe (pentru cine vrea mai mult)

Sortare prin numărare (Counting Sort). Dacă valorile sunt mici (≤ 10⁶), nu compari deloc: numeri cât de des apare fiecare valoare și le scrii în ordine. Timp O(n + V). Este ideea vectorului de frecvență din lecția 6.

Merge sort și quick sort. Sortările rapide (O(n log n)) se bazează pe divide et impera: împart vectorul, sortează părțile, le combină. Interclasarea din lecția următoare este chiar „combinarea” din merge sort. Le vei scrie în clasa a XI-a.

Sortare cu comparator propriu. sort(a+1, a+n+1, [](int x, int y){ return sc(x) < sc(y); }); sortează după orice criteriu, fără să rescrii algoritmul. Funcțiile lambda sunt o unealtă comună în C++ modern.

Stabilitate. O sortare e stabilă dacă elementele egale rămân în ordinea inițială. Bulele și inserția sunt stabile, selecția cu interschimbări nu. Contează când sortezi înregistrări (nume) după un criteriu (nota), păstrând ordinea alfabetică dintre cei cu aceeași notă.

Rezumat

  • Bule: vecini + repetare până nu mai e nicio interschimbare.
  • Selecție: minimul din rest pe poziția i.
  • Inserție: inserezi a[i] în partea sortată din stânga.
  • Criteriul de sortare = condiția din if. sort() pentru viteză.
  • Cele trei metode simple sunt O(n²); sort e O(n log n).

Fișa de lucru

Ai citit lecția? Printează fișa sau deschide-o pe ecran și rezolvă exercițiile în ordine.

Fișă de lucru · 6 pagini · 90 min

Sortări

  • Urmărești pas cu pas bulele, selecția și inserția și numeri treceri, comparații, interschimbări.
  • Alegi metoda potrivită pentru date aproape sortate, valori mici sau vectori uriași.
  • Sortezi după un criteriu, ții împreună doi vectori paraleli și sortezi doar o parte.

Te-ai blocat la un exercițiu?

Probleme de lucru

Începe cu acestea, în ordine. Problemele se deschid pe pbinfo.ro, unde trimiți soluția și primești punctajul.

  • ordonare#509

    Scrie bulele de mână, fără sort().

    ușoară
  • sortare#129

    Descrescător, din fișier.

    ușoară
  • sortprime#510

    ușoară

Temă

Rezolvă-le singur și bifează ce ai terminat. Bifele rămân salvate în acest browser.

  • ksort#511

    ușoară
  • sortmax#512

    ușoară
  • sort10#4146

    ușoară
  • sortcif#130

    Criteriu: suma cifrelor.

    ușoară
  • sortpp#183

    Sortezi doar o parte, restul rămân pe loc.

    medie
  • sortpie#514

    medie
  • sortsd#515

    medie

Pentru cei care vor mai mult

  • sortare-divizori#1608

    medie
  • aliniere#533

    medie

Grile din subiectele de BAC

Exerciții de tip grilă din variantele de Bacalaureat. Se rezolvă pe pbinfo.ro, care îți verifică imediat răspunsul.

Citește și exersează în plus

  • Sortarea tablourilor · pbinfo.ro
  • Metoda bulelor · pbinfo.ro
  • Sortarea prin selecție · pbinfo.ro
  • Sortarea prin inserție · pbinfo.ro
  • VisuAlgo — Sorting · visualgo.net

    animații pas cu pas pentru bule, selecție, inserție și altele; poți introduce propriul vector

  • Toptal — Sorting Algorithms Animations · toptal.com

    compară vizual viteza algoritmilor pe date aleatoare, aproape sortate, inversate

  • cppreference — std::sort · en.cppreference.com

    referința pentru sortarea din biblioteca standard

Te-ai blocat la lecția asta?

Scrie-mi ce nu iese și vedem împreună de unde se blochează.

Răspunsuri

Exersează pe hârtie

1. (3, 6, 1, 5, 8). Comparări: 6 și 3 (interschimb → 3 6 8 1 5); 6 și 8 (nu); 8 și 1 (interschimb → 3 6 1 8 5); 8 și 5 (interschimb → 3 6 1 5 8).

2. 6 interschimbări: pentru i = 1 sunt 3 (4↔3, 3↔2, 2↔1), pentru i = 2 sunt 2, pentru i = 3 este 1: total 6.

3. Criteriul: a[i] trebuie să fie înaintea lui a[i+1] dacă ambele sunt pare și a[i] < a[i+1], sau a[i] e par și a[i+1] impar, sau ambele impare și a[i] > a[i+1]. Interschimbi când nu e îndeplinit:

#include <iostream>
#include <algorithm>
using namespace std;

int a[1001], n;

bool inainte(int x, int y)       // true dacă x trebuie să fie înaintea lui y
{
    bool px = x % 2 == 0, py = y % 2 == 0;
    if (px != py) return px;     // parul înaintea imparului
    if (px) return x <= y;       // pare crescător
    return x >= y;               // impare descrescător
}

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i < n; i++)
        for (int j = i + 1; j <= n; j++)
            if (!inainte(a[i], a[j]))
                swap(a[i], a[j]);
    for (int i = 1; i <= n; i++)
        cout << a[i] << ' ';
    return 0;
}

4. Pe (2, 1, 3, 4, 5): 2 treceri (prima interschimbă 2 cu 1, a doua nu găsește nimic). Pe (5, 4, 3, 2, 1): 5 (patru treceri cu interschimbări + una de verificare).

5. (1, 2, 3): 3 > 1 interschimbare → (1, 3, 2); 3 > 2 interschimbare → (1, 2, 3).

6. a) și d). Varianta a) pune pe poziția i maximul; b) și c) sortează crescător.

7. Pe un vector aproape sortat, inserția face foarte puține mutări (fiecare element e deja aproape de locul lui): se apropie de O(n), pe când bulele fac tot câte o trecere de verificare pentru fiecare element aflat „în urmă”.