Tehnici de sortare

Sortare prin bule

Sortare prin inserare

Sortarea prin selecț ie

Sortare Rapidă
Sortare prin îmbinare
 Sortare prin bule

Aici DATĂ este un tablou cu N elemente. Acest algoritm

sortează elementele DATE.
BULĂ(DATA, N)
• Repetă paș ii 2 ș i 3 pentru K=1 până la N-1.
• SetPTR:=1. [Iniț ializează pointerul PTR.]
• Repeț i cât PTR ≤ N-K: Executaț i Pas.
1. Dacă DATA[PTR] > DATA[PTR + 1], atunci:
Schimbă DATA[PTR] cu DATA[PTR + 1].
[Eid of If structure]
• SetPTR:=PTR +1.
[Eid ofiiier loop]
[Eid-ul-Ș tept 1 bucla exterioară.]

[Link]şire.
 Exemplu de Bubble Sort
7 28 5 4 2 75 48 2 547 8 2 45 7 8

2 785 4 2 7548 2 547 8 2 4 5 7 8

2 7854 2 5748 2 45 7 8 (finalizat)

2 7 584 2 5 47 8

2 7 5 48

Pas 1 Pass 2 Pass 3 Treacă 4

 Bubble SortComplexity
Analiza complexităț ii metodei Bubble sort:
În mod tradiț ional, timpul pentru sortarea unui tablou este măsurat în
termeni de număr de comparaț ii. Numărul f(i) al
comparisoisii bubble sort este uș or de calculat.
În mod specific, există i-1 comparaț ii în timpul primei treceri,
i-2 comparisoisii secoid pass aid so oi.
Astfel, f(i) = (i-1) + (i-2) + ------- + 2 + 1
= i(i-1)/2 = i / 22 – i/2
= O(i 2)
Astfel, timpul necesar pentru a sorta un ș ir folosind sortarea prin bule
metoda proporț ională i unde i2este numărul de
Introducerea elementelor. Astfel, complexitatea sortării
2 prin bule este O(i)
 Sortare prin inserare

SORTARE_INSERTIE (A, N)
[Link][0] = -∞.
[Link]ă paș ii 3 până la 5 pentru K = 2, 3, …, N:
[Link] = A[K] ajuta PTR = K - 1.
[Link] ț i în timp ce TEMP < A[PTR]:
(a) SetA[PTR+1] = A[PTR]
(b) SetPTR = PTR - 1.
Eid de Loop.
[Link][PTR+1] = TEMP.
[Eid-ul Loop 2.]
[Link].
 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ă fac schimb.
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ă.
locaț ii adecvate între
8 32 34 51 6421
Algoritmul vede 21 ca un alt număr mai mic ș i se mută
iito betweei8aid32.
Numerele sortate fiial:
8 21 32 34 51 64
 Iisertoi SortComplexity
Acest algoritm de sortare este folosit frecvent atunci când este foarte mic.

Cazul cel mai rău apare când elementele din array sunt în ordine inversă. Ciclu lor trebuie să
foloseș te comparaț ii K - 1.

f(i) = 1 + 2 + 3 + ….+ (i – 1)
= i(i – 1)/2
O(i ) 2

În medie, vor fi aproximativ (K - 1)/2 comparaț ii.

loop-ul lor.
f(i) = (1 + 2 + 3 + ….+ (i – 1))/2
= i(i – 1)/4
= O(i 2)
 Sortare prin selecț ie
Acest algoritm sortează un tablou A cu N elemente.
SELECȚ IE(A, N)
[Link]ă paș ii 2 ș i 3 pentru k=1 până la N-1:
[Link] ț i MIN(A, K, N, LOC).
3.[A schimbare A[k] ș i A[LOC]]
SetTemp:= A[k], A[k]:= A[LOC] ajuta A[LOC]:=Temp.
[Sărbătoarea pasului 1 Loop.]
[Link]ș ire.
MIN(A, K, N, LOC).
[Link] := A[K] ajuta LOC:= K.
2. Repeta pentru j = k + 1 la N:
Dacă Mii > A[j], atunci: SetMii := A[j] ș i LOC := J.
Structura oficiului Eid
[Link].
 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
 Selectoi SortComplexity
Numărul de compara ț ii ale sortării prin selec ț ie
algoritmul necesită păstrarea ordinii originale a elementelor.
Există i-1 compara ț ii dure în timpul trecerii 1 pentru a găsi
cel mai mic element, i-2 compari durin trecerea 2to fi
elementul secundar cel mai mic, ajută să o fac.
În consecinț ă,
f (i) = (i-1)+(i-2)+-----+2+1
= i(i-1)/2
= O(i 2)
Funcț ia f(i) are aceeaș i valoare O(i) atât2 pentru cel mai rău caz
caz mediu de ajutor.
 Algoritm de sortare rapidă
PARTIȚIONARE(A, ÎNCEPUT, SFÂRȘ IT, LOC)

1.1- SetLEFT = BEG, RIGHT=END, LOC=BEG

2.2- [Scai de la dreapta la stânga]
(a) Repetă atâta timp cât A[LOC] <= A[RIGHT] iar LOC != RIGHT
DREPTUL = DREPTUL-1
[Eid al Loop]
(b) Dacă LOC == DREAPTA atunci returnează
(c) Dacă A[LOC] > A[RIGHT] atunci
(i) schimb A[LOC] ș i A[RIGHT]
(ii) SetLOC = RIGHT
Structura ofi Eid
3.3- [Scai din stânga în dreapta]
(a) Repetă cât timp A[LEFT] <= A[LOC] ș i LEFT != LOC
STÂNGA = STÂNGA + 1

Eid-ul Loop
(b) Dacă LOC == STÂNGA atunci returnează
(c) Dacă A[STÂNGA] > A[LOC] atunci
(i) Iiterchaige A[STÂNGA] ș i A[LOC]
(ii) SetLOC = LEFT
(iii) Mergi la pasul 2.
[Structura oficiului Eid]
 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 în timp ce TOP != -1

4.4- [Pop sublistă din stive]

SetBEG = LOWER[TOP] , END = UPPER[TOP]
TOP = TOP – 1
5- Apelare PARTITION (A, ÎNCEPUT, SFÂRȘ IT, LOC)
6- [Împinge lista sublistoitelor în stive când are 2 sau mai multe elemente]
Dacă BEG < LOC-1thei
a. TOP = TOP + 1
b. LOWER[TOP] = BEG
c. UPPER[TOP] = LOC-1
[Eid ofif Structure]
7- [Împinge sublistă dreaptă în stive când are 2 sau mai multe elemente]
Dacă LOC+1 < ENDthei
a. TOP = TOP + 1
b. LOWER[TOP] = LOC+1
c. SUPERIOR[TOP] = SFÂRȘ IT

[Structura Eid ofif]

Eidul etapei 3 a buclei
8- Ieș ire
 Complexitatea sortării rapide
Cazul cel mai rău
O(i 2)

Caz mediu
O(i log i)
 Sortare prin îmbinare

• Împărț iț i ajutorul Coiquer

• Structura recursivă
– Împărț iț iproblema sub-problemele care sunt similare
la original, dar de dimensiuni mai mici
– Conqueresub-problemele prin rezolvarea lor
recursiv. Dacă sunt suficient de mici, rezolvă-le doar
Este o chestiune simplă.
– Combinasolutoisto pentru a crea un solutoitothe
problema originală
 Exemplu AI: Sortare prin îmbinare

Problema de sortare: Sorta

sequeice ofnelemeitsiito
ordonanț ă de decreta

Împarte:Dvidetthen-elemeitsequeicet sortate
două subsecvenț e de n/2 elemente fiecare
Conquer:Sorcele două subsecuenț e recursiv
usiig ordonare prin divizare
Combine:Mergecele două subsequence sortate pentru
producea răspunsul sortat.
 Sortare prin îmbinare - 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 91 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 26 32 6 43 15 9 1

18 26 32 6 43 15 9 1
 Sortare prin îmbinare(A, p, r)
o secvenț ă denumerele stocate în array A
o secvenț ă ordonată denumere

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 SortarePrinInterclasare(A,p,q)

4 MergeSort(A,q+1,r)
5 Fuzionare(A,p,q,r) //fuzionează A[p..q] cu A[q+1..r]

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

 Procedura de Combinare
Fuzionare(A,p,q,r)
1n1 q–p+ 1
2n2 r–q Array conț inând subarrays sortate
3pentrueu 1 tonă1 A[p..q] ș i A[q+1..r].
4 faceL[i] A[p+i– 1]
5pentruj 1 tonă2
Subarray sortat combinat în A[p..r].
6 făR[j] A[q+j]
7L[n1+1
8R[n2+1
9i 1
10j 1
11pentruk plar
12 fa dacăL[i] R[j]
13 atunciA[k] L[i]
14 eu i+ 1
15 altfelA[k] R[j]
16 j j+ 1
 Îmbinare – Exemplu

A … 1 6 8 9 26 32 42 43 …

L 6 8 26 32
R 1 9 42 43

eu
 Analiza Sortării prin Îmbinare
Timpul de execuț ie T(n) pentru Sortarea prin Interclasare:
Împărț iț i: calculul mediei necesită (1)
Coiquer: solviig 2 sub-probleme iau 2T(n/2)
Combiie: mergiignelemeitstakes (n)
Total:
T(n)= (1)ifn =1
T(n)=2T(n/2)+ (n)ifn >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)
 Comparaț ia 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 îmbinare
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