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
- Ideea de sortare
- Metoda bulelor (Bubble Sort)
- Sortarea prin selecție (Selection Sort)
- Sortarea prin inserție (Insertion Sort)
- Comparație
- Sortarea după un criteriu
- sort() din STL
- Greșeli frecvente
- La BAC
- Exersează pe hârtie
- Mai departe (pentru cine vrea mai mult)
- Rezumat
- Fișa de lucru
- Probleme de lucru
- Temă
- Pentru cei care vor mai mult
- Grile din subiectele de BAC
- Citește și exersează în plus
- Răspunsuri
Fișiere PDF și de lucru
- Lecția în PDF
versiunea de printat
- Fișa de lucru: Sortări
6 pagini · 90 min
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.
#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.
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ă.
#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ătorDe ș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²);
sorte 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.
- ușoară
- ușoară
- ușoară
sortprime#510
https://www.pbinfo.ro/probleme/510/sortprime
Temă
Rezolvă-le singur și bifează ce ai terminat. Bifele rămân salvate în acest browser.
Pentru cei care vor mai mult
- medie
sortare-divizori#1608
https://www.pbinfo.ro/probleme/1608/sortare-divizori
- medie
aliniere#533
https://www.pbinfo.ro/probleme/533/aliniere
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.
- #1038care secvență ordonează descrescător elementele unui tablou
https://www.pbinfo.ro/?pagina=itemi-evaluare&id=1038
- #1036parcurgere cu condiție: produsul elementelor pare
https://www.pbinfo.ro/?pagina=itemi-evaluare&id=1036
- #1039efectul unor modificări succesive pe un vector
https://www.pbinfo.ro/?pagina=itemi-evaluare&id=1039
Citește și exersează în plus
- Sortarea tablourilor · pbinfo.ro
https://www.pbinfo.ro/articole/5587/sortarea-tablourilor
- Metoda bulelor · pbinfo.ro
https://www.pbinfo.ro/articole/5589/metoda-bulelor
- Sortarea prin selecție · pbinfo.ro
https://www.pbinfo.ro/articole/5605/sortarea-prin-selectie
- Sortarea prin inserție · pbinfo.ro
https://www.pbinfo.ro/articole/5609/sortarea-prin-insertie
- VisuAlgo — Sorting · visualgo.net
animații pas cu pas pentru bule, selecție, inserție și altele; poți introduce propriul vector
https://visualgo.net/en/sorting
- Toptal — Sorting Algorithms Animations · toptal.com
compară vizual viteza algoritmilor pe date aleatoare, aproape sortate, inversate
https://www.toptal.com/developers/sorting-algorithms
- cppreference — std::sort · en.cppreference.com
referința pentru sortarea din biblioteca standard
https://en.cppreference.com/w/cpp/algorithm/sort
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ă”.