Algoritmi pentru sortarea
vectorilor
Andrei Yannis Matei si Asaftei Calin
Sortarea? Ce este aia?
Sortarea este o operatie fundamentala in informatica.
Putem sorta datele pentru prezentarea catre utilizator (de exemplu in agenda telefonica, sau atunci
cand navigam printre foldere, sau selectam o anumita melodie din telefon)
Sortarea este o piatra fundamentala in algoritmii mai mari, pentru ca simplifica anumite cerinte
(precum gasirea unei chei unice, sau detectarea elementelor duplicate)
Putem sorta orice, numere, texte, orice care are un criteriu de sortare. Dar pentru usurinta vom folosii
numere in toate exemplele noastre. Aveti grija sa distingeti pozitia elementului (i) de elementul efectiv (
V[i] ).
Sortarea prin selectie (selection sort)
!!Complexitatea timpului poate fi
Sortarea prin selecție (Selection Sort) se bazează pe următoarea vazuta din structurarea celor doua
for-uri. Indiferent de elementele din
idee: vector, acest algoritm executa (N – 1)
+ (N – 2) + … + 3 + 2 + 1 comparari.
● fie un vector X[] cu n elemente;
● plasăm în X[0] cea mai mică valoare din vector; Daca adunam obtinem N * (N – 1) / 2,
● plasăm în X[1] cea mai mică valoare rămasă; ceea ce prescurtat inseamna O(N2).
● etc.
O descriere a algoritmului este:
● parcurgem vectorul cu indicele i
○ parcurgem cu indicele j elementele din dreapta lui X[i]
■ dacă elementele X[i] și X[j] nu sunt în ordinea dorită, le
interschimbăm
Observații
● în algoritmul de mai sus, pentru fiecare valoare a lui i, în X[i] se obține cea mai
mică (mare) valoare dintre elementele cu indici i, i+1, ..., n; altfel spus, pentru
fiecare i, în X[i] se selectează minimul (maximul) dintre elementele i, i+1, ..., n.
● metoda se mai numește sortare prin selecție directă, sortare prin selecție
implicită sau sortare prin interschimbare.
Avem si note!!
Mai multe exemple!! Sorteaza Preturi!!!
Metoda Bulelor (Bubble Sort)
Cunoscută și sub numele BubbleSort, metoda bulelor se bazează pe
următoare idee:
● fie un vector X[] cu n elemente
● parcurgem vectorul și pentru oricare două elemente învecinate care
nu sunt în ordinea dorită, le interschimbăm valorile
● după o singură parcurgere, vectorul nu se va sorta, dar putem
repeta parcurgerea
● dacă la o parcurgere nu se face nicio interschimbare, vectorul este
sortat
O reprezentare a algoritmului este:
● cat timp vectorul nu este sortat
○ presupunem că vectorul este sortat
○ parcurgem vectorul
■ dacă două elemente învecinate nu sunt în
ordinea dorită
■ le interschimbăm
■ schimbăm presupunerea inițială
!!Sortarea prin metoda bulelor este o metoda de sortare simpla, eficienta pentru
un numar mic de elemente ( max 15-20), dar nu si pentru tablouri mari. Timpul
de executie depinde de ordinea initiala a elementelor. Daca tabloul este deja
sortat e nevoie de un singur pas, adica N-1 comparari. In cazul cel mai
nefavorabil sunt necesare N x (N-1)/2 comparari si N x (N-1)/2 interschimbari.
Performanta algoritmului in caz general este mai greu de analizat dar este
asemanatoare cazului nefavorabil
.
Sortează prin metoda bulelor un vector cu n termeni Sa se aranjeze descrescator elementele unui
(n<=100) în ordine crescătoare. vector
Sortarea prin insertie Sorteaza Varste!!
Sortarea prin inserție (Insertion Sort) se bazează pe următoarea
idee:
● fie un vector X[] cu n elemente;
● dacă secvența cu indici 0, 1, …, i-1 este ordonată, atunci
putem insera elementul X[i] în această secvență astfel încât
să fie ordonată secvența cu indici 0, 1, …, i-1, i.
● luăm pe rând fiecare element X[i] și îl inserăm în secvența
din stânga sa
● la final întreg vectorul va fi ordonat
Algoritm
O reprezentare a algoritmului este:
● parcurgem vectorul cu indicele i
○ inserăm pe X[i] în secvența din stânga sa; pentru
inserare se mută unele elemente din secvență spre
dreapta
Primul “for” efectueaza O(n) iteratii, iar al doilea, in cel mai rau caz,
tot O(n). Prin urmare, complexitatea in timp a sortarii prin insertie
este O(n^2). Cel mai rau caz este atins atunci cand vectorul dat
este sortat invers ( descrescator ). Cel mai bun caz, in care
algoritmul ruleaza in O(n), este cel in care vectorul e deja sortat
Vom sorta temperaturi.
Mai sus, vom sorta prin
insertie