Tehnici de sortare

Sortare prin bulă

Sortare prin inserț ie
Sortare prin selecț ie
Sortare rapidă
Sortare prin îmbinare
 Sortare prin bule

Aici DATA este un array cu N elemente. Acest algoritm

sortează elementele din DATE.
BUBBLE(DATA, N)
[Link] ț i pa ș ii 2 ș i 3 pentru K=1 până la N-1.
[Link] PTR:=1. [Ini ț iaț i pointerul de trecere PTR.]
[Link] ț i cât timp PTR≤N-K: Executa ț i Pasul.
a) DACA DATA[PTR] > DATA[PTR + 1], atunci:
Schimbă DATA[PTR] cu DATA[PTR + 1].
[Sfârș itul structurii If]
b) Seta ț i PTR:=PTR +1.
[Sfârș itul buclei interioare]
[Sfârș itul Paș ului 1 bucla exterioară.]

[Link] ș ire.
 Exemplu de sortare prin bulă

7 28 5 4 2 7 5 48 2 5 4 7 8 2 45 7 8

2 78 5 4 2 7548 2 547 8 2 4 5 7 8

2 785 4 2 5748 2 45 7 8 (finalizat)

2 7 5 84 2 5 4 7 8

2 7 5 48

Trecerea 1 Pass 2 Pass 3 Trecerea 4

 Complexitatea sortării prin bule

Analiza complexită ț ii metodei Bubble sort:

În mod tradiț ional, timpul pentru sortarea unui tablou este măsurat în
termeni ai numărului de comparaț ii. Numărul f(n) de
comparările în sortarea prin bule sunt u ș or de calculat.
În mod specific, există n-1 comparaț ii în timpul primei treceri,
n-2 comparări în a doua trecere ș i aș a mai departe.
Astfel, f(n) = (n-1) +(n-2) +-------+2+1
= n(n-1)/2 = n2/ 2–n/2
= O(n2)
Astfel, timpul necesar pentru a sorta un array folosind sortarea prin bule
metoda este propor ț ională cu n2unde n este numărul de
introduceț i elementele. Astfel, complexitatea sortării cu bule este O(n2)
 Sortare prin inserț ie

SORTARE_INSERTIE (A, N)
[Link] A[0] = -∞.
[Link] ț i Pa ș ii 3 până la 5 pentru K = 2, 3, …, N:
3. Setează TEMP = A[K] ș i PTR = K –1.
[Link]ă în timp ce TEMP < A[PTR]:
(a) Setează A[PTR+1] = A[PTR]
(b) Setează PTR = PTR–1.
[Sfârș itul Buclăi.]
[Link] A[PTR+1] = TEMP.
[Sfârș itul Bucla 2.]
6. Întoarcere.
 Exemplu de Sortare prin Inserție
Sort: 34 8 64 51 32 21
34 864 51 32 21
Algoritmul vede că 8 este mai mic decât 34, aș a că îl schimbă.
8 3464 5132 21
51 este mai mic decât 64, aș a că se swap.
8 34 51 6432 21
8 34 51 643221 (din diapozitivul anterior)

Algoritmul vede 32 ca pe un alt număr mai mic ș i îl mută

la locul său corespunzător între 8 ș i 34.
8 32 34 51 6421
Algoritmul vede 21 ca pe un alt număr mai mic ș i se miș că
între 8 ș i 32.
Numerele finale sortate:
8 21 32 34 51 64
 Complexitatea Sortării prin Inserț ie

Acest algoritm de sortare este frecvent utilizat atunci când n este foarte
mic

Cel mai rău caz apare când array-ul este în ordine inversă. Interiorul
bucla trebuie să folosească K–1 comparaț ii.

f(n) = 1 + 2 + 3 +….+ (n –1)

= n(n–1)/2
= O(n2)

În medie, va fi aproximativ (K –1)/2

comparatii in bucla interioara.
f(n) = (1 + 2 + 3 +….+ (n –1))/2
= n(n–1)/4
 Sortare prin selecț ie
Acest algoritm sortează un tablou A cu N elemente.
SELECȚ IE(A, N)
[Link] ț i pa ș ii 2 ș i 3 pentru k=1 până la N-1:
2. Apelare MIN(A, K, N, LOC).
3. [Schimbaț i A[k] cu A[LOC]]
Setează Temp:= A[k], A[k]:= A[LOC] ș i A[LOC]:=Temp.
[Sfârș itul pasului 1 Loop.]
[Link]şire.
MIN(A, K, N, LOC).
1. Setează MIN := A[K] ș i LOC := K.
2. Repeta ț i pentru j=k+1 până la N:
Dacă Min>A[j], atunci: Setează Min:= A[j] ș i LOC:=J.
[Sfârș itul structurii if]
3. Întoarcere.
 Exemplu de Sortare prin Selecț ie

8 4 6 9 2 3 1 1 2 3 4 9 6 8

1 4 6 9 2 3 8 1 2 3 4 6 9 8

1 2 6 9 4 3 8 1 2 3 4 6 8 9

1 2 3 9 4 6 8 1 2 3 4 6 8 9
 Complexitatea sortării prin selecț ie

Numărul f(n) de comparaț ii în sortarea prin selecț ie

algoritmul este independent de ordinea originală a
elemente. Există n-1 compara ț ii în timpul
trece ț i 1 pentru a găsi cel mai mic element, n-2
comparatii in timpul trecerii 2 pentru a gasi al doilea
cel mai mic element, ș i aș a mai departe.

În consecinț ă,
f (n) = (n-1)+(n-2)+-----+2+1
= n(n-1)/2
= O(n2)
The f (n) holds the same value O(n2) both for
 Algoritmul Quick sort
PARTITION(A, ÎNCEPUT, SFÂRȘ IT, LOC)
1.1- Setează LEFT = ÎNCEPUT, RIGHT=SFÂR Ș IT, LOC=ÎNCEPUT

2.2- [Scana ț i de la dreapta la stânga]

(a) Repetaț i cât timp A[LOC] <= A[RIGHT] ș i LOC != RIGHT
DREAPTA = DREAPTA-1
[Sfârș itul ciclului]
(b) Dacă LOC == DREAPTA atunci returnează
(c) Dacă A[LOC] > A[RIGHT] atunci
(i) Schimbă A[LOC] ș i A[RIGHT]
(ii) Setează LOC = DREAPTA
[Sfârș itul structurii if]
3.3- [Scanare de la stânga la dreapta]
(a) Repetă cât timp A[LEFT] <= A[LOC] ș i LEFT != LOC
LEFT = LEFT+1
[Sfârș itul buclei]
(b) Dacă LOC == STÂNGA atunci returnează
(c) Dacă A[STÂNGA] > A[LOC] atunci
(i) Schimbaț i A[STÂNGA] ș i A[LOC]
(ii) Setează LOC = STÂNGA
(iii) Mergi la pasul 2.
[Sfârș itul structurii if]
 Algoritmul quick sort
QUICKSORT()
1.1- TOP = -1
2.2- Dacă N > 1 atunci TOP = TOP + 1, LOWER[TOP] = 0, UPPER[TOP] = N-1
3.3- Repeta ț i pa ș ii 4 până la 7 atâta timp cât TOP != -1

4.4- [Pop sublist din stive]

Setaț i BEG = LOWER[TOP], END = UPPER[TOP]
TOP = TOP–1
5- Apelaț i PARTITION (A, ÎNCEPUT, SFÂRȘ IT, LOC)
6- [ Impinge sublista stângă pe stive când are 2 sau mai multe elemente]
Dacă BEG < LOC-1 atunci
a. TOP = TOP + 1
b. LOWER[TOP] = BEG
c. UPPER[TOP] = LOC-1
[Sfârș itul structurii if]
7- [ Împinge sublista dreaptă pe stive atunci când are 2 sau mai multe elemente ]
Dacă LOC+1 < FINAL atunci
a. TOP = TOP+1
b. LOWER[TOP] = LOC+1
c. SUPRA[TOP] = SFÂRȘ IT
[Sfârș itul structurii if]
[Sfârș itul buclei pasului 3]

8- Ieș ire
 Complexitatea sortării rapide

Cazul cel mai rău

O(n2)

Caz mediu
O(n log n)
 Sortarea prin îmbinare

Împarte și cucerește
•Recursiv în structură
–Împărțiți problema în sub-probleme care sunt
similar cu originalul, dar mai mic ca dimensiune
Conquistasub-problemele prin rezolvarea lor
recursiv. Dacă sunt destul de mici, doar rezolvă
ei într-un mod direct.
–Combinăsoluț iile pentru a crea o soluț ie pentru
problema originală
 Un Exemplu: Sortare prin Interclasare

Problema de sortare: Sortează o secvenț ă de n elemente în

ordinea non-decreș terii.

Împărț iț i: Împărț iț i secvenț a de elemente de ordin care urmează să fie sortată

în două subsecvenț e de n/2 elemente fiecare
Conquer: Ordena ț i cele două subsecuen ț e recursiv folosind
sortare prin interclasare.

Combina: Combină cele două subsecvenț e sortate pentru a

produceț i răspunsul sortat.
 Sortare prin interclasare–Exemplu
Secvenț ă originală Secvenț ă sortată

18 26 32 6 43 15 9 1 1 6 9 15 18 26 32 43

18 26 32 6 43 15 9 1 6 18 26 32 1 9 15

18 26 32 6 43 15 9 1 18 26 6 32 15 43 1 9

18 26 32 6 43 15 9 1 18 2632 6 43 15 9 1

18 26 32 6 43 115599 1
 Sortare prin îmbinire (A, p, r)

o secvenț ă de numere stocată în array A

o secvenț ă ordonată de numere

MergeSort(A,p,r) // sorteazăA[p..r] prin împărț ire ș i cucerire

1 dacă p<r
2 apoi q (p+r)/2
3 Sortarea prin fuziune(A,p,q)

4 MergeSort(A,q+1,r)
5 Îmbină(A,p,q,r) //îmbină A[p..q] cu A[q+1..r]

Apel iniț ial: MergeSort(A, 1,n)

 Procedura Îmbinare
Îmbină(A,p,q,r)
1n1 q–p+ 1
2n2 r–q Array care conț ine subarray-uri sortate
3pentrueu 1 tonă1 A[p..q] ș i A[q+1..r].
4 făL[i] A[p+i–1]
5pentruj 1ton2
Output:Merged sorted subarray inA[p..r].
6 faceR[j] A[q+j]
7L[n1+1]
8R[n2+1]
9i 1
10j 1
11pentruk plar
12 fă dacăL[i] R[j]
13 atunciA[k] L[i]
14 eu i+ 1
15 altfelA[k] R[j]
16 j j+ 1
 Fuzionare - Exemplu

A … 1 6 89 26 32 42 43 …

L R 1 9 42 43

eu
 Analiza Sortării prin Îmbinare

Timpul de execuț ie T(n) al Merge Sort:

Împărț iț i: calcularea medianei durează (1)
Conquer: rezolvarea a 2 sub-probleme durează 2T(n/2)
Combinare: fucidare elemente durează (n)
Total:
T(n)= (1) dacă n = 1
T(n)=2T(n/2)+ (n) dacă n > 1
T(n) = 2T(n/2) + n
=2 ((n/2)log(n/2) + (n/2)) +n
= n(log(n/2)) + 2n
=nlogn–n+ 2n
=nlogn+n
=O(nlogn)
 Compararea algoritmilor

Best Average Worst

Caz Caz Caz
Sortare prin bule O(n) O(n2) O(n2)
Sortare prin inserț ie O(n) O(n2) O(n2)
Sortare prin selecț ie O(n2) O(n2) O(n2)
Sortare prin fuziune O(n log n) O(n log n) O(n log n)
Sortare rapidă O(n log n) O(n log n) O(n2)
Sortare prin grămadă O(n log n) O(n log n) O(n log n)
Mulț umesc