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

Comparat ,ie teoretic a s ,i experimental a a unor
metode de sortare
Vanciu C at alin-Marian
Departamentul de Informatic a
Facultatea de Matematic a  si Informatic a
Universitatea de Vest Timi soara, Rom^ ania
Email: [anonimizat]
1

Rezumat
Studiul este dedicat metodelor de sortare  si compar arii acestora.
Vom analiza cazul favorabil, cazul defavorabil, cazul mediu, dar si care
algoritm este mai util, in functie de datele de intrare.
Cazul favorabil corespunde acelor instant ,e ale problemei pentru care
num arul de operat ,ii efectuate este cel mai mic.
Cazul defavorabil corespunde instant ,elor pentru care num arul de operat ,ii
efectuate este maxim.
Cazul mediu reprezint a valoarea medie a timpilor de execut ,ie calculat a
^ n raport cu distribut ,ia de probabilitate corespunz atoare spat ,iului datelor
de intrare.
2

Cuprins
1 Introducere 4
2 Vericarea corectitudinii algoritmilor 5
3 Descrierea s ,i implementarea algoritmilor de sortare 6
3.1 Quick Sort: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
3.2 Merge Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
3.3 Insertion Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
3.4 Selection Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
3.5 Bubble Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
4 Studiu de caz 12
5 Concluzii 14
3

1 Introducere
Prin sortare ( Algoritmi  si structuri de date , Burdescu Dumitru
Dan, 1992) se ^ nt ,elege procesul de rearanjare a unei mult ,imi date
de obiecte, ^ ntr-o ordine specicat a de utilizator. Scopul operat ,iei
de sortare este de a facilita g asirea ulterioar a a membrilor mult ,imii
date. Interesul primordial ^ n procesul de sortare este atribuit teh-
nicilor fundamentale care se folosesc ^ n construirea algoritmilor de
rezolvare a unor probleme de programare. Procesul de sortare este
astfel un subiect ideal pentru a se demonstra diversitatea algoritmi-
lor de rezolvare.
Problema sort arii s ,i a comparat ,iei metodelor de sortare o s a r am^ an a
^ ntotdeauna interesant a datorit a evolut ,iei rapide a informaticii. O s a
se creeze noi metode de sortare, poate mai rapide, poate mai lente,
nes ,tiind asta dac a nu le vom analiz a pe ecare ^ n parte.
^In cele ce urmeaz a, o s a a
 am care metod a de sortare este cea mai
ecient a, dar s ,i care este cea mai inecient a, care algoritmi sunt
stabili, dar s ,i cei care sunt instabili.
O s a observ am c a, nu ^ ntotdeauna, cea mai ecient a metod a de
sortare, este s ,i cea mai potrivit a.
Exemplu simplu:
O s a spunem c a avem de sortat 20 de numere reale.
Nu este relevant s a folosim un algoritm de sortare ^ n care putem
stoca 10.000 de elemente, deoarece ocup am memorie degeaba.
De aceea, vom folosi un algoritm care sorteaz a minimul de elemente
necesare, f ar a a ocup a prea mult a memorie.
Exemplu complex: Ne g^ andim c a avem de f acut un proiect denumit
"bibliotec a".
Pentru^ nceput, trebuie s a sortam autorii^ n ordine alfabetic a, urm^ and
c a apoi s a ad aug am genurile scrise de autor (comedie, drama, nuvela,
roman etc.).
Dup a ce am sortat dup a nume s ,i am ad augat genurile, trebuie s a
sortam cresc ator c art ,ile, dup a anul public arii (dar s ,i gen), pentru
ecare autor ^ n parte.
La nal, c^ and biblioteca o s a e funct ,ioanala s ,i o s a e ^ mprumutate
s,i returnate c art ,ile, noi trebuie s a t ,inem evident ,a. De aceea, vom
construi un program care s a ment ,in a ordinea, s a ret ,in a ce c art ,i au
fost ^ mprumutate (s ,i p^ an a la ce dat a), precum s ,i ce c art ,i au fost
returnate (programul rearanj^ andu-le automat ^ n list a, ^ n ordinea co-
respunz atoare, astfel ^ nc^ at s a r am^ an a sortat totul).
4

2 Vericarea corectitudinii algoritmilor
Conform c art ,iiIntroducere ^ n proiectarea s ,i analiza algoritmilor (D.
Zaharie), un algoritm este considerat corect dac a permite obt ,inerea
rezultatului problemei pornind de la datele init ,iale ale acesteia. Pen-
tru a obt ,ine informat ,ii privind abilitatea unui algoritm de a rezolva
problema pentru care a fost proiectat se poate alege una dintre
urm atoarele variante: experimental a sau analitic a.
Varianta experimental a: se testeaz a algoritmul pentru diverse instant ,e
ale problemei. Principalul avantaj este c a nu necesit a tehnici pentru
a  aplicat a, pe c^ and principalul dezavantaj ^ l reprezint a faptul c a
testarea nu poate acoperi ^ ntotdeauna toate variantele posibile de
date de intrare. Varianta experimental a permite uneori identica-
rea situat ,iilor pentru care algoritmul nu funct ,ioneaz a corect, ^ ns a nu
garanteaz a ^ ntotdeauna corectitudinea.
Varianta analitic a: se demonstreaz a c a algoritmul funct ,ioneaz a co-
rect pentru orice dat a de intrare. Principalul avantaj ^ l reprezint a
faptul c a este garantat a corectitudinea pentru orice dat a de intrare.
Dezavantajul este reprezentat de faptul c a, uneori, este dicil de
g asit o demonstrat ,ie.
^In varianta analitic a a corectitudinii se parcurg urm atoarele etape
principale:
1. Identicarea propriet at ,ilor datelor de intrare(preconditiile pro-
blemei).
2. Identicarea propriet at ,ilor pe care trebuie s a le satisfac a datele
de ies ,ire (postconditiile problemei).
3. Demonstrarea faptului c a pornind de la precondit ,ii s ,i aplic^ and
prelucr arile specicate^ n algoritm se ajunge la satisfacerea postcondit ,iilor.
5

3 Descrierea s ,i implementarea algoritmilor de
sortare
3.1 Quick Sort:
Este un celebru algoritm de sortare, dezvoltat de C.A.R.
Hoare s ,i care, ^ n medie efectueaz a nlog n comparat ,ii, pen-
tru a sorta n elemente. Acesta a fost dezvoltat de C.A.R.
Hoare ^ n 1960, pe c^ and lucra la mica rma britanic a pro-
duc atoare de calculatoare Elliot Brothers.
Algoritmul se bazeaz a pe tehnica Divide et Conquer s ,i
funct ,ioneaz a astfel: se alege un pivot s ,i pune toate ele-
mentele mai mici c a acesta ^ n st^ anga lui, iar pe cele mai
mari ^ n dreapta (tehnic a numit a partit ,ie).
Nu este un algoritm stabil !
Implementare:
int partitie(int x[], int li, int ls){//x[li..ls]
int pivot = x[ls]; // pivot
int i = (li – 1); // index-ul celui mai mic element
for (int j = li; j <= ls – 1; j++)
{
if (x[j] < pivot)
{
int aux = x[i];
x[i] = x[j];
x[j] = aux;
}
}
int auxx = x[i+1];
6

x[i+1] = x[ls];
x[ls] = auxx;
return (i + 1);
}
int QuickSort(int x[], int li, int ls){
if(li < ls){
int q = partitie(x, li, ls);
QuickSort(x, li, q-1);
QuickSort(x, q+1, ls);
}
}
3.2 Merge Sort
Este un algoritm de sortare cu complexitatea O(nlog n), inventat de
John von Neumann ^ n 1945. Este un exemplu de algoritm de tip
Divide et Impera. Acesta ^ mparte lista nesortat a ^ n dou a subliste;
sorteaz a ecare sublist a, iar apoi se interclaseaza cele dou a liste s ,i
se obt ,ine lista init ,ial a sortat a.
Este un algoritm stabil !
7

Implementare:
void merge(int x[], int li, int m, int ls)
{
int i, j, k;
int n1 = m – li + 1;
int n2 = ls – m;
int L[n1], R[n2];
for (i = 0; i < n1; i++)
L[i] = x[li + i];
for (j = 0; j < n2; j++)
R[j] = x[m + 1+ j];
i = 0;
j = 0;
k = li;
while (i < n1 && j < n2)
{
if (L[i] <= R[j])
{
x[k] = L[i];
i++;
}
else
{
x[k] = R[j];
j++;
}
k++;
}
while (i < n1)
{
x[k] = L[i];
i++;
k++;
}
while (j < n2)
{
x[k] = R[j];
j++;
k++;
}
}
8

void mergeSort(int x[], int li, int ls){
if (li < ls)
{
int m = abs((li+ls)/2);
mergeSort(x, li, m);
mergeSort(x, m+1, ls);
merge(x, li, m, ls);
}
}
3.3 Insertion Sort
^Incepand cu al doilea element al tabloului x[1..n], ecare element
este inserat pe pozitia adecvat a ^ n subtabloul care ^ l precede.
Este un algoritm stabil !
Implementare:
void insertie(int x[], int n){
int i, j, aux;
for(i = 2; i <= n; i ++)
{
aux = x[i];
j = i – 1;
}
while(j >= 1 && aux < x[j]){
x[j+1] = x[j];
j = j – 1;
}
x[j+1] = aux;
}
9

3.4 Selection Sort
Algoritmul ^ mparte lista de intr ari ^ n dou a p art ,i: o sublist a sor-
tat a de elemente s ,i o sublist a a celorlalte elemente nesortate care
ocup a restul listei. Algoritmul continu a g asind cel mai mic (sau cel
mai mare, ^ n funct ,ie de ordinea de sortare) din sublista nesortat a,
schimb^ and-o cu elementul cel mai din st^ anga, nesortat (as ,ez^ andu-l^ n
ordine ordonat a) s ,i mut^ and limitele sublistei un element la dreapta.
A fost inventat de Oscar Wilde ^ n timpul migrat ,iilor Bantu.
Nu este un algoritm stabil !
Implementare:
void selectie(int x[], int n){
for(int i = 1; i < n; i++){
int k = i;
for(int j = i+1; j <= n; j++)
if(x[k] > x[j])
k = j;
if(k < i)
{
int aux = x[i];
x[i] = x[k];
x[k] = aux;
}
}
}
10

3.5 Bubble Sort
Sortarea cu bule, denumit a uneori sortare de scufundare, este un al-
goritm de sortare simplu care paseaz a^ n mod repetat prin list a, com-
par a elementele adiacente s ,i le schimb a dac a sunt ^ n ordine gres ,it a.
Trecerea prin list a se repet a p^ an a la sortarea listei.
Nu este un algoritm stabil !
Implementare:
void BubbleSort(int x[], int n){
for(int i = 0; i < n; i++)
for(int j = i+1; j <= n; j++)
if(x[i] > x[j]){
int aux = x[i];
x[i] = x[j];
x[j] = aux;
}
}
Implementarea algoritmilor de mai sus a fost f acut a in
C++.
11

4 Studiu de caz
^In acest capitol, vom pune ^ n practic a algoritmii evident ,iati mai
sus. Propriet at ,ile calculatorului pe care vor  testate seturile de
date sunt: procesor Intel(R) Core(TM) i5-2430M CPU, 2.40 GHz,
Windows 7.
Pentru^ nceput, vom observa complexitatea ec arui algoritm^ n cazul
favorabil, cazul mediu, precum s ,i cazul defavorabil.
Tabela 1: Complexitatea algoritmilor de sortare
Metoda Caz favorabil Caz mediu Caz defavorabil
Quick Sort
(n)(nlogn ) O(n2)
Merge Sort
(nlogn )(nlogn ) O(nlog n)
Insertion Sort
(n) (n2) O(n2)
Selection Sort
(n2) (n2) O(n2)
Bubble Sort
(n2) (n2) O(n2)
Urmeaz a s a facem o serie de teste pentru a vedea timpul de execut ,ie
pentru tablourile cu elemente as ,ezate pe pozit ,ii aleatoare, dar s ,i
pentru elementele as ,ezate ^ n ordine descresc atoare.
Tabela 2: Sortarea tablourilor – generare aleatoare de numere
Metoda 10 100 1.000 10.000 100.000 1.000.000
Quick Sort 0.015 0.03 0.053 0.064 1.358 –
Merge Sort 0.016 0.017 0.031 0.035 0.074 –
Insertion Sort 0.02 0.028 0.06 0.104 7.582 –
Selection Sort 0.015 0.04 0.042 0.188 15.514 –
Bubble Sort 0.008 0.017 0.041 0.452 45.050 –
12

Tabela 3: Sortarea tablourilor – generare numere in ordine descrescatoare
Metoda 10 100 1.000 10.000 100.000 1.000.000
Quick Sort 0.016 0.045 0.031 0.058 1.411 –
Merge Sort 0.03 0.03 0.036 0.037 0.062 –
Insertion Sort 0.033 0.052 0.042 0.105 7.424 –
Selection Sort 0.032 0.034 0.032 0.192 15.450 –
Bubble Sort 0.031 0.036 0.048 0.409 44.493 –
Metodele de sortare prin insert ,ie, select ,ie s ,i prin metoda
bulelor au performant ,e bune c^ and s ,irul de sortat are di-
mensiuni reduse. ^Ins a, pentru s ,iruri de dimensiuni mari
folosim sortarea prin interclasare(Merge Sort) sau sorta-
rea rapid a(Quick Sort). Pentru listele care au cel put ,i 1
milion de elemente, programele nu mai funct ,ioneaz a.
13

5 Concluzii
^In lucrare este prezentat a compararea unor metode de sortare care
urm ares ,te a
area celei mai eciente metode de sortare. Astfel, am
observat c a cea mai ecient a metod a de sortare nu este ^ ntotdeauna
cea mai rapid a s ,i cea care poate ret ,ine multe elemente, ci cea mai
potrivit a pentru lista ce trebuie sortat a.
Am observat c a Insertion Sort, Bubble Sort s ,i Selection Sort au
acceas ,i complexitate ^ n cazul defavorabil, ^ ns a, ^ n practic a, se poate
observ a c a Bubble Sort este mai inecient dec^ at ceilalti algoritmi,
datorit a celor dou a cicluri. Putem observa, de asemenea, c a Quick
Sort-ul, pe listele mari, este mai put ,in ecient dec^ at Merge Sort-ul.
Concluzia celor enunt ,ate mai sus este c a algoritmul Merge Sort este
foarte ecient pe listele de mari dimensiuni, spre deosebire de Quick
Sort, care, dup a cum se poate observa, are o durat a mult mai mare
fat , a de primul algoritm. De asemenea, se poate observa c a Insertion
Sort, Bubble Sort s ,i Selection Sort sunt cele mai eciente pe listele
de dimensiuni mici, p^ an a ^ n 100 de elemente ( av^ and s ,i un avantaj
c a pot  implementate destul de us ,or, dup a cum s-a observat).
14

Bibliograe
Introducere ^ n proiectarea s ,i analiza algoritmilor (Daniela Zaharie)
Algoritmi s ,i struturi de date (Burdescu Dumitru Dan, 1992)
15