Comparat ,ie teoretic a s ,i experimental a a unor [628472]

Comparat ,ie teoretic a s ,i experimental a a unor
metode de soratre
Andreea-Mariana Br anescu
Aprilie 2019
Universitatea de Vest din Timis ,oara
Facultatea de Matematic a s ,i Informatic a
Specializarea Informatic a
Email: [anonimizat].
Aceast a lucrare este dedicat a studiului asupra unor metode de sortare,
av^ and ca scop realizarea unei comparat ,ii ^ ntre acestea.
Prin sortare^ nt ,elegem un algoritm prin intermediul c aruia putem rearanja
un num ar oarecare de elemente^ ntr-o anumit a ordine. Un exemplu de folosire
a sort arii ^ l reprezint a motoarele de c autare web, cum ar  Google, Yahoo,
MSN, care folosesc astfel de algoritmi.
^In cele ce urmeaz a vom prezenta unii dintre cei mai cunoscut ,i algoritmi
de sortare s ,i vom analiza comportamentul acestora ^ n diferite situat ,ii, pentru
a putea realiza o comparat ,ie ^ ntre aces ,tia.
1

1 Introducere
De multe ori ne ^ ntreb am de ce avem nevoie de at^ at de mult ,i algoritmi de
sortare? Se s ,tie faptul c a nu tot ,i algoritmii au fost dezvoltat ,i ^ n acelas ,i timp.
^Incerc am s a ^ nv at , am diferit ,i algoritmi de sortare pentru a ^ nt ,elege anumite
concepte s ,i tehnici care stau la baza acestora.
Algoritmii ce urmeaz a a  analizat ,i sunt Bubble Sort, Selection Sort,
Insertion Sort, Merge Sort s ,i Quick Sort. ^In cazul ec arui algoritm vom
analiza timpul de execut ,ie s ,i memoria utilizat a pentru a determina ecient ,a,
iar mai apoi vom studia comportamentul algoritmilor ^ n cazuri mai speciale,
precum listele cu un num ar foarte mare de elemente.
Consider am o secvent , a de entit at ,i. Aceste entit at ,i pot  de diferite tipuri.
Pentru a exemplica s ,i a face sortarea mai us ,or de ^ nt ,eles, vom vorbi despre
numere. Numerele noastre apart ,in unei mult ,imi, mult ,ime pe care exist a o
relat ,ie de ordine.
Sortarea secvent ,eipresupune aranjarea elementelor astfel ^ nc^ at acestea
s a se a
e ^ ntr-o anumit a ordine, cresc atoare sau descresc atoare.
De ce facem aceast a analiz a s ,i, implicit, aceast a comparat ,ie? Pentru a
^ nt ,elege mai bine sortarea, deoarece pe baza sort arii sunt construit ,i mult ,i
alt ,i algoritmi. Astfel, vom c^ as ,tiga un avantaj ^ n ceea ce prives ,te rezolvarea
problemelor viitoare cu care ne vom confrunta.
2 Prezentare formal a a problemei s ,i solut ,iei
Anumit ,i algoritmi necesit a timp p atratic de execut ,ie, at^ at ^ n cazul mediu,
c^ at s ,i ^ n cazul cel mai nefavorabil. Prin aceasta ^ nt ,elegem c a aces ,ti algoritmi
se comport a excelent pentru cazuri ^ n care avem liste mici de elemente, ^ ns a
cu c^ at num arul de elemente cres ,te, cu at^ at ecient ,a scade, av^ and nevoie de
un timp foarte mare de execut ,ie. De asemenea, exist a algoritmi mai ecient ,i,
care lucreaz a ^ n timp logaritmic, ceea ce ^ i face mult mai utili pentru cazurile
mari. Pentru a ^ nt ,elege diferent ,a dintre un timp p atratic s ,i unul logaritmic
este sucient s a spunem c a pe un caz de 100.000 de elemente, QuickSort va
sorta lista ^ n aproximativ 30 de secunde, pe c^ and MergeSort are nevoie de
peste nou a ore.
Vom ^ nv at ,a care algoritm se potrives ,te cel mai bine cu problema de re-
zolvat, analiz^ and capacitatea ec aruia.
2

2.1 Bubble Sort
Figure 1: Sortare prin metoda bulelor
Bubble Sort a fost ment ,ionat a pentru prima dat a de Knuth[1]. Sortarea
prin metoda bulelor mai este cunoscut a s ,i sub numele de sortare prin inter-
schimbarea valorilor vecine. De altfel, acesta este s ,i fundamentul pe care se
construies ,te algoritmul.
Pseudocod
Bubblesort ( x [ 1 . . . n ] )
FOR i <n,2 ,1 DO
FOR j <1 , i1 DO
IF x [ j ] >x [ j +1] THEN x [ j] <>x [ j +1]
ENDIF
ENDFOR
ENDFOR
RETURN x [ 1 . . . n ]
Ideea de baz a a acestuia este de a parcurge tabloul de la st^ anga la dreapta,
compar^ and elementele vecine, x[i] s ,ix[i+ 1]. Dac a se g asesc dou a elemente
care nu sunt ^ n ordinea dorit a, valorile lor vor  interschimbate.
2.2 Selection Sort
Metoda de sortare prin select ,ie este considerat a a  una dintre cele mai simple
metode de sortare. Se s ,tie faptul c a lucreaz a bine pe liste mici, ^ ns a nu d a
rezultate bune ^ n ceea ce prives ,te vectorii deja ordonat ,i.
Pseudocod
S e l e c t i o n ( x [ 1 . . . n ] )
FOR i <1,n1 DO
k<i ;
FOR j <i +1,n DO
IF x [ k] >x [ j ] THEN k <j ENDIF
3

ENDFOR
IF k< >i THEN x [ i] <>x [ k ]
ENDIF
ENDFOR
RETURN x [ 1 . . . n ]
Algoritmul funct ,ioneaz a astfel: pentru ecare pozit ,ie, pe care o vom
nota cu i, ^ ncep^ and de la prima, se caut a cel mai mic element din sub-
tabloul x[i:::n]. Dup a ce elementul cu valoarea cea mai mic a este g asit, va
 interschimbat cu elementul de pe pozit ,ia curent a, apoi trecem la pozit ,ia
urm atoare.
2.3 Insertion Sort
Figure 2: Sortare prin insert ,ie
Algoritmul de sortare prin insert ,ie este util atunci c^ and avem un num ar
mic de elemente. De asemenea, aceast a metod a de sortare mai poate  util a
atunci c^ and lista este aproape sortat a. O proprietate important a este faptul
c a ^ n cazul s ,irurilor aproape sortate comportarea algoritmului este apropiat a
de comportarea din cazul cel mai favorabil.
4

Pseudocod
I n s e r t i o n ( x [ 1 . . . n ] )
FOR i <2 ,n DO
aux<x [ i ]
j<i1
WHILE ( j >=1) AND ( aux <x [ j ) ) DO
x [ j +1] <x [ j ]
j<j1
ENDWHILE
x [ j +1] <aux
ENDFOR
RETURN x [ 1 . . . n ]
Sortarea prin insert ,ie seam an a^ ntr-o anumit a m asur a cu sortarea prin select ,ie.
Ideea de baz a este urm atoarea: ^ ncep^ and cu al doilea element al tabloului
x[1:::n], ecare element este inserat pe pozit ,ia adecvat a ^ n subtabloul care ^ l
precede.
2.4 Merge Sort
Figure 3: Animat ,ie MergeSort
5

Merge Sort sau sortarea prin interclasare utilizeaz a metoda Divide et
Impera, o tehnic a de divizare. Ideea de baz a a acestei tehnici este descom-
punerea problemei init ,iale ^ n mai multe subprobleme de acelas ,i tip, dar de
dimensiune mai mic a. Subproblemele sunt rezolvate aplic^ and aceeas ,i tehnic a,
iar dac a este necesar, solut ,iile obt ,inute prin rezolvarea subproblemelor sunt
combinate.
^In prezentarea pseudocodului pentru urm atorii doi algoritmi vom folosi
notat ,iile follosite de Steven Skiena ^ n The Algorithm Design Manual [2], us ,or
adaptate pentru a  mai us ,or de ^ nt ,eles.
Algoritmii bazat ,i pe compararea elementelor prezentat ,i anterior au or-
dinul de complexitate O(n2). Ideea de start o reprezint a ^ ncercarea de a
reduce aceast a complexitate folosind principiul diviz arii.
As ,adar, vom descompune secvent ,a init ,ial a ^ n dou a subsecvent ,e pe care
le vom ordona ulterior, folosind aceeas ,i tehnic a, iar ^ n nal vom combina
subsecvent ,ele ordonate pentru a obt ,ine un s ,ir ordonat.
Altfel spus, se ^ mparte s ,irul ^ n secvent ,e c^ at mai mici, astfel ^ nc^ at ecare
secvent , a s a e ordonat a la un moment dat s ,i interclasat a cu o alt a secvent , a
din vector.
Pseudocod
s o r t a r e ( x [ s . . . d ] )
IF s<d THEN
m<( s+d) DIV 2 // d i v i z a r e
x [ s . . .m] <s o r t a r e ( x [ s . .m] ) // r e z o l v a r e
x [m+ 1 . ; . d ] <s o r t a r e ( x [m+1..d ] )
x [ s . . . d ] <i n t e r c l a s a r e ( x [ s . .m] , x [m+1..d ] ) // combinare
ENDIF
RETURN x [ s . . d ]
Mai jos prezent am algoritmul de interclasare.
i n t e r c l a s a r e ( x [ s . . .m] , x [m+ 1 . . . d)
i<s ; j <m+1;
k<0 ;
WHILE i <= m AND j <=d DO
k<k+1
IF x [ i ] <=x [ j ] THEN t [ k ] <x [ i ]
i<i+1
ELSE
t [ k ] <x [ j ]
6

j<j+1
ENDIF
ENDWHILE
WHILE i <= m DO
k<k+1
t [ k ] <x [ i ]
i<i+1
ENDWHILE
WHILE j <=d DO
k<k+1
t [ k ] <x [ j ]
j<j+1
ENDWHILE
RETURN t [ 1 . . . k ]
2.5 Quick Sort
Figure 4: Sortarea rapid a
Tehinca folosit a de Quick Sort sau sortarea rapid a este aceeas ,i pe care
o foloses ,te s ,i Merge Sort, anume tehnica diviz arii. Prin urmare, aces ,ti doi
algoritmi sunt mai ecient ,i, ^ ntruc^ at se reduce complexitatea problemei. S ,i^ n
cazul sort arii rapide folosim notat ,iile din The Algorithm Design Manual[2].
7

Pseudocod
q u i c k s o r t ( x [ s . . . d ] )
IF s<d THEN
q<pivot ( x [ s . . d ] )
x [ s . . . q1]<quicksort1 ( x [ s . . . q 1])
x [ q + 1 . . . d ] <quicksort1 ( x [ q + 1 . . . d ] )
ENDIF
RETURN x [ s . . d ]
Construim pivotul:
pivot ( x [ s . . . d ] )
v<x [ d ]
i<s1
j<d
WHILE i <j DO
REPEAT i <i+1 UNTIL x [ i ] >=v
REPEAT j <j1 UNTIL x [ j ] <=v
IF i<j THEN x [ i] <>x [ j ] ENDIF
ENDWHILE
x [ i ] <>x [ d ]
RETURN i
Diferent ,a dintre Quick Sort s ,i Merge Sort se observ a at^ at ^ n etapa de-
scompunerii s ,irului init ,ial ^ n subs ,iruri, c^ at s ,i ^ n etapa de recombinare a rezul-
tatelor.
3 Implementarea problemei s ,i solut ,iei
Vom lucra ^ n CodeBlocks, implementarea algoritmilor o vom face ^ n C++.
Sistemul de operare este Windows 10 Pro, sistem de operare pe 64 de bit ,i,
procesor Intel(R) Celeron(R) CPU 1000M @1.80GHz, procesor de tip x64.
3.1 Bubble Sort
^In cazul mediu, Bubble Sort are complexitatea O(n2), iar memoria folosit a
esteO(1). Algoritmul este stabil, cu condit ,ia s a se foloseasc a inegalitate
strict a[1].
8

Algoritm
void bubble ( i n t a [ ] , i n t n)
f
i n t i , schimbat , aux ;
do
f
schimbat = 0 ;
f o r ( i = 0 ; i <n1; i++)
i f ( a [ i ] <a [ i +1])
f
aux = a [ i ] ;
a [ i ] = a [ i +1];
a [ i +1] = aux ;
schimbat = 1 ;
g
gwhile ( schimbat ) ;
g
3.2 Selection Sort
Complexitatea algoritmului de sortare prin select ,ie^ n cazul mediu este aceeas ,i
cu cea a sort arii prin interschimbarea valorilor vecine, mai exact O(n2).
Memoria folosit a este tot O(1), ^ ns a acest algoritm nu prezint a stabilitate[1].
Algoritm
void s e l e c t i o n ( i n t a [ ] , i n t n)
f
i n t i , aux , min , minat ;
f o r ( i = 0 ; i <n1 ; i++)
f
minat = i ;
min = a [ i ] ;
f o r ( j = i + 1 ; j <n ; j++)
f
i f ( min >a [ j ] )
f
minat = j ;
9

min = a [ j ] ;
g
g
aux = a [ i ] ;
a [ i ] = a [ minat ] ;
a [ minat ] = aux ;
g
g
3.3 Insertion Sort
S,i ^ n cazul sort arii prin insert ,ie complexitatea algoritmului este O(n2), iar
memoria folosit a este O(1). Sortarea prin insert ,ie este stabil a[1].
Algoritm
void i n s e r t i o n ( i n t a [ ] , i n t n)
f
i n t i , j , aux ;
f o r ( i = 1 ; i <n ; i++)
f
j = i ;
while ( j >0 && a [ j1 ]>a [ j ] )
f
aux = a [ j ] ; a [ j ] = a [ j 1 ] ; a [ j] = aux ;
g
g
g
3.4 Merge Sort
Merge Sort se bazeaz a pe tehnica diviz arii, ceea ce duce la o ^ mbun at at ,ire a
complexit at ,ii.
^In cazul mediu, metoda de sortare bazat a pe interclasare se ^ ncadreaz a
^ nO(nlogn ). As ,a cum era de as ,teptat, acest avantaje aduce dup a sine s ,i
dezavantaje. Memoria utilizat a este O(n).
10

Algoritm
void mergesort ( i n t a [ ] , i n t st , i n t m, i n t dr )
f
i n t b [ 1 0 0 ] ;
i n t i , j , k ;
i = 0 ; j = s t ;
while ( j <= m)
b [ i ++] = a [ j ++];
i = 0 ; k = s t ;
while ( k <j && j <= dr )
i f (b [ i ] <= a [ j ] )
a [ k++] = b [ i ++];
e l s e
a [ k++] = a [ j ++];
while ( k <j )
a [ k++] = b [ i ++];
g
void merge ( i n t a [ ] , i n t st , i n t dr )
f
i f ( s t <dr )
f
i n t m = ( s t+dr ) / 2 ;
merge ( a , st , m) ;
merge ( a ,m+1, dr ) ;
mergesort ( a , st , m, dr ) ;
g
g
3.5 Quick Sort
Quick Sort este unul dintre cei mai rapizi s ,i cei mai utilizat ,i algoritmi de
sortare p^ an a ^ n acest moment. Des ,i cazul cel mai nefavorabil este O(n2), ^ n
practic a sortarea rapid a d a rezultate mai bune dec^ at alt ,i algoritmi de sortare
din clasa O(nlogn ). Memoria folosit a este O(logn), ceea ce prezint a ^ nc a un
avantaj, iar algoritmul este stabil[2].
11

Algoritm
void qSort ( i n t vector [ ] , i n t st , i n t dr )
f
i n t temp , min , max, m i j l ;
m i j l = vector [ s t +(dr s t ) / 2 ] ;
min = s t ; max = dr ;
do
f
while ( vector [ min ] <m i j l ) min++;
while ( vector [ max ] >m i j l ) max;
i f ( min <= max)
f
temp = vector [ min ] ;
vector [ min++] = vector [ max ] ;
vector [ max] = temp ;
g
gwhile ( min <= max ) ;
i f ( s t <max) qSort ( vector , st , max ) ;
i f ( dr >min ) qSort ( vector , min , dr ) ;
g
4 Studiu de caz
Din punct de vedere teoretic, cunoas ,tem faptul c a primii trei algoritmi prezentat ,i,
Bubble Sort, Selection Sort s ,i Insertion Sort, necesit a timp p atratic de execut ,ie,
ceea ce ^ nseamn a c a se comport a bine ^ n cazul listelor cu put ,ine elemente,
^ ns a au nevoie de un timp de execut ,ie mult mai mare ^ n cazul listelor cu un
num ar mare de elemente. Merge Sort s ,i Quick Sort folosesc tehnica Divide
et Impera, lucru care conduce la sortarea unei liste cu un num ar mare de
elemente ^ n timp logaritmic, algoritmii ind mult mai ecient ,i.[1]
Sortare prin interschimbarea elementelor vecine este considerat a a  una
dintre cele mai put ,in eciente metode de sortare, ^ ns a cu un algoritm relativ
simplu.[1]
Despre sortarea prin select ,ie cunoas ,tem faptul c a d a rezultate bune pe
cazuri mici,^ ns a^ n cazul vectorilor mari, d a rezultate mai slabe dec^ at sortarea
prin insert ,ie sau cea care utilizeaz a metoda bulelor.[1]
12

Spre deosebire de alt ,i algoritmi, sortarea prin inset ,ie este foarte des
folosit a pentru sortarea tablourilor cu un num ar mic de elemente, ^ ns a s ,i
aici ^ nt^ ampin am probleme atunci c^ and dimensiunea vectorului cres ,te.[1]
Sortarea prin interclasare s ,i sortarea rapid a dau am^ andou a rezultate bune.
Cazul cel mai nefavorabil la Merge Sort este O(n), iar la Quick Sort este
O(n2). Deci, din punct de vedere teoretic, Merge Sort este mai puternic
dec^ at Quick Sort.
Pentru realizarea experimentului, vom lua^ n considerare timpul de execut ,ie
al ec arui algoritm ^ n trei situat ,ii diferite: c^ and vectorul este deja ordonat,
c^ and vectorul este ordonat dar ^ n ordine invers a s ,i c^ and elementele vectorului
sunt ^ n ordine aleatorie.
Pentru generarea vectorului cu elemente ^ n ordine aleatorie am folosit
urm atoarea secvent , a:
i n t arraySize = 10000 ;
i n t array [ arraySize ] ;
srandom ( time (NULL) ) ;
f o r ( i n t i = 0 ; i <s i z e ; i++)
array [ i ] = random ( ) % s i z e ;
^In situat ,ia ^ n care avem un vector deja ordonat, obt ,inem urm atoarele
rezultate:
100 elemente 1.000 elemente 10.000 elemente 100.000 elemente
Bubble Sort 0.040 ms 0.017 ms 0.057 ms 0.022 ms
Insertion Sort 0.003 ms 0.004 ms 0.005 ms 0.004 ms
Selection Sort 0.004 ms 0.018 ms 0.040 ms 0.047 ms
Merge Sort 0.012 ms 0.023 ms 2.16 ms 20.35 ms
Quick Sort 0.12 ms 3.73 ms 295.01 ms 29937.61 ms
Dup a cum se poate vedea, ^ n acest caz cel mai bine funct ,ioneaz a Insertion
Sort, av^ and timp de execut ,ie relativ mic.Pe de cealalt a parte, cele mai slabe
rezultate au fost obt ,inute de Quick Sort.
^In situat ,ia ^ n care vectorul este ordonat, dar ^ n ordine invers a, am obt ,inut
urm atoarele rezultate:
13

100 elemente 1.000 elemente 10.000 elemente 100.000 elemente
Bubble Sort 0.092 ms 5.95 ms 445.46 ms 44793.96 ms
Insertion Sort 0.049 ms 3.17 ms 259.75 ms 25116.82 ms
Selection Sort 0.052 ms 3.08 ms 316.27 25314.63 ms
Merge Sort 0.017 ms 0.23 ms 2.34 ms 21.68 ms
Quick Sort 0.060 ms 5.86 ms 438.67 ms 44020.01 ms
^In acest caz cel mai mic timp de execut ,ie este obt ,inut de Merge Sort. La
polul opus se a
 a Bubble Sort.
^In cazul^ n care elementele vectorului se a
 a^ n ordine aleatorie, rezultatele
obt ,inute sunt:
100 elemente 1.000 elemente 10.000 elemente 100.000 elemente
Bubble Sort 0.050 ms 5.93 ms 445.92 ms 44677.46 ms
Insertion Sort 0.016 ms 1.72 ms 126.75 ms 12516.42 ms
Selection Sort 0.020 ms 2.18 ms 235.74 ms 23677.25 ms
Merge Sort 0.016 ms 0.22 ms 2.45 ms 29.36 ms
Quick Sort 0.011 ms 0.16 ms 1.67 ms 20.01 ms
^In ultima situat ,ie cel mai bun timp de execut ,ie ^ l ofer a Quick Sort, as ,a
cum era de as ,teptat, iar cele mai slabe rezultate sunt oferite de Bubble Sort.
5 Comparat ,ie cu literatura
^InThe Algorithm Design Manual [2], Steven Skiena^ ncearc a s a atrag a atent ,ia
asupra problemei sort arii. Conform spuselor acestuia, majoritatea ideiloi
interesante ^ n design-ul algoritmilor apar ^ n contextul sort arii, as ,a cum este
metoda Divide et Impera sau algoritmii randomizat ,i.
Acesta mai arm a c a numeroase probleme importante pot  reduse la
sortare, as ,adar e indicat s a folosim algoritmi cu timp logaritmic de execut ,ie.
Ideea principal a e c a multe probleme devin mult mai us ,or de rezolvat, din
moment ce itemii sunt sortat ,i.
De asemenea, ^ n cartea sa, Introduction to Algorithms , Cormen[3] arm a
c a mult ,i programatori consider a problema sort arii a  una dintre problemele
fundamentale ^ n studiul algoritmilor.
14

6 Concluzii s ,i direct ,ii viitoare
^In urma execut arii algoritmilor bazat ,i pe metodele de sortare prezentate,
putem arma c a algoritmul care utilizeaz a Insertion Sort este cel mai ecient
^ n cazul listelor mici, deja ordonate, av^ and cel mai mic timp de execut ,ie.
^In cazul ^ n care listele au un num ar mare de elemente, dar sunt ordonate
^ n ordine invers a, cele mai bune rezultate sunt oferite de Merge Sort.
^In ultima situat ,ie, c^ and vectorul este sortat aleator, cel mai bine se com-
port a Quick Sort. Contrar as ,tept arilor, ^ ntruc^ at Quick Sort nu este consid-
ert a cea mai ecient a metod a de sortare ^ n cazul listelor mari, s-a demostrat
experimental c a pe o list a cu un num ar total de 100.000 de elemente Quick
Sort are cel mai mic timp de execut ,ie.
La polul opus, cu cele mai slabe rezultate ^ n toate cele trei situat ,ii prezen-
tate, se a
 a, as ,a cum era de as ,teptat, Bubble Sort.
Ca direct ,ie viitoare se consider a utilizarea diverselor metode de sortare
pentru simplicarea rezolv arii unor probleme.
References
[1] The Art of Computer Programming-Volum 3 – Donald E. Knut
[2] The Algorithm Design Manual – Steven S. Skiena
[3] Introduction to Algorithms – Thomas H. Cormen, Charles E. Leiserson,
Ronald L. Rivest, Cliord Stein
15