Post on 15-Oct-2015
MINISTERUL EDUCAIEI
INSTITUTUL DE FORMARE CONTINU
CATEDRA TEHNOLOGII INFORMAIONALE
Structuri de date
(n baza C++)
SUPORT DE CURS
Ediia 2
Elaborat i adaptat
Sergiu Pereteatcu, conf., dr.
Alexandru Pereteatcu, mag. n inf.
Chiinu - 2014
Structuri de date (n baza C++): Suport de curs S.Pereteatcu, A.Pereteatcu
2
R ec o ma n da t d e c t r e C o mi s ia t i i n i f i c o -M et o d i c a Uns t i t u t u lu i d e F or ma r e C o nt i nu , P r oc es s + v e r b a l nr . 1 d i n 1 4 iu n i e 2 0 1 2
Sergiu Pereteatcu, confereniar unuversitar, doctor
Alexandru Pereteatcu, magistru n informatic
Redactor coordonator
Ion Spinei - confereniar unuversitar, doc
Tehnoredactare computerizat
Ion Stngu
Descrierea CIP a Camerei Naionale a Crii
Pereteatcu, Sergiu Structuri de date (n baza C++): Suport de curs / Sergiu Pereteatcu, Alexandru Pereteatcu;
Inst. de Formare Continu, Catedra Tehnologii Informaionale. Ch.: Inst. de Formare Continu, 2012. 135 p.
Bibliogr.: p. 134 (15 tit.). ISBN 978-9975-4404-3-1.
004.6:519.1/6(075.8)
P52
Structuri de date (n baza C++): Suport de curs S.Pereteatcu, A.Pereteatcu
3
CUPRINS
1. INTRODUCERE N STRUCTURI DE DATE ..................................................................4
1.1. Noiuni generale .............................................................................................................4 1.2. Clase de baz..................................................................................................................5
2. TABELE ................................................................................................................................10 2.1. Noiune de tabel............................................................................................................10 2.2. Tabele neordonate ........................................................................................................12 2.3. Tabele neordonate structurate arborescent.....................................................................17 2.4. Tabele ordonate ............................................................................................................24 2.5. Tabele cu adresare direct.............................................................................................29 2.6. Tabele de repartizare (repartizarea aleatorie).................................................................29
3. TEHNICI DE SORTARE ...................................................................................................40 3.1. Noiuni generale ...........................................................................................................40 3.2. Clase pentru exemple de sortare....................................................................................41 3.3. Sortarea prin interschimbare .........................................................................................44 3.4. Sortarea rapid..............................................................................................................45 3.5. Sortarea prin inserie.....................................................................................................59 3.6. Sortarea prin selecie.....................................................................................................66 3.7. Sortarea arborescent (piramidal, heapsort).................................................................66 3.8. Comparaii practice ai diferiilor algoritmi de sortare ....................................................72
4. STRUCTURI DINAMICE DE DATE................................................................................73 4.1. Noiune de structura dinamic de date...........................................................................73 4.2. Arbori binari.................................................................................................................74 4.3. Liste .............................................................................................................................85 4.4. Stive .............................................................................................................................95 4.5. Cozi............................................................................................................................118
5. MATRICE ...........................................................................................................................129 5.1. Noiune de matrice......................................................................................................129 5.2. Structura intern de memorie vector.........................................................................130 5.3. Reprezentarea matricelor n memoria operativ ..........................................................130 5.4. Reprezentarea matricelor pe linii .............................................................................131 5.5. Reprezentarea matricelor pe coloane .......................................................................140 5.6. Vectori definitori ........................................................................................................147 5.7. Vectori Iliffe...............................................................................................................153
6. ACTIVITI ........................................................................................................................161 I Declararea claselor de baz....................................................................................161 II Lucrul cu tabele....................................................................................................162 III Sortri.................................................................................................................162 IV Structuri dinamice de date...................................................................................163 V Matrice ................................................................................................................165
BIBLIOGRAFIE........................................................................................................................166
Structuri de date (n baza C++): Suport de curs S.Pereteatcu, A.Pereteatcu
4
Program = Algoritm + Structuri de date
Niklaus Wirth, 1976
1. INTRODUCERE N STRUCTURI DE DATE
1.1. Noiuni generale Definiia:
Prin structura de date abstract (SDA), sau pur i simplu structura de date
(SD), vom nelege o totalitate de reguli i restricii ce reflect legturile existente ntre prile separate de date i prin care prile acestea se unesc
ntr-un singur tot.
Cuvntul abstract n definiia structurii de date subliniaz c structura de date se examineaz fr cercetarea modului de reprezentare a ei n memoria calculatorului.
Structura nimic nu ne spune despre prile separate de date (mai corect despre coninutul lor). Coninutul poate fi format n procesul de lucru. Drept vorbind, structura poate s cear ca aceste prile componente s fie n concordan cu structura. Totui orice informaii ce se conin n elementele de date nici cum nu depind de nsi structura.
Termenul utilizat element nseamn o parte de structur de date abstract. Elementul poate fi o valoare de un tip simplu. El poate fi i o alt structur de date, sau o referin la alte structuri de date, astfel s creeaz structuri de date ierarhice sau secvene de structuri de date.
Vom diviza structuri de date n statice i dinamice. Definiia:
Exemplu: Matrice cu dimensiunile fixe, Tabeel cu numrul de nregistrri tabelare fix, Vectori cu numrul de elemente fix. Definiia:
Prin structura de date dinamic vom nelege aa SD, la care n procesul de
lucru se schimb att informaii ce se conin n elemente de date, ct i numrul de elemente (componena cantitativ).
Exemplu: Liste nlnuite de diferite tipuri, stive, cozi, arbori binari.
Prin structura de date static vom nelege aa SD, la care n procesul de lucru se schimb numai informaiile ce se conin n elemente de date i nu se schimb
cantitatea acestor elemente.
Structuri de date (n baza C++): Suport de curs S.Pereteatcu, A.Pereteatcu
5
1.2. Clase de baz
La demonstrarea metodelor de organizare a structurilor de date vom utiliza clase generice. Orice astfel de metod va fi realizat printr-o clas generic parametrizat cu o alt clas-parametru ce reprezint un element al structurii de date respective. n calitate de argumentul la instaniera unei clase generice vom folosi o clas concret derivat de la clasa abstract elem.
Clasa abstract elem nu va putea fi instaniat. Ea doar descrie cele funcii virtuale pure care neaprat trebuie redefinite n orice clasa derivat concret, care va fi folosit ulterior pentru reprezentarea elementelor la construirea structurilor de date. Clasa abstract mai conine suprancrcrile operatorilor de comparaie bzndu-le pe funcia virtual pur cmp().
Declararea clasei abstracte elem va arta astfel: #include
#include
#include
#include
#include
#include
//
// a b s t r a c t c l a s s "e l e m"
//
class elem
{
public:
virtual int fscanf_el(FILE *f)=0;
virtual void show(const char* opening=NULL,
const char* ending=NULL)=0;
virtual int free() = 0;
virtual int cmp(elem& e2) = 0;
int operator > (elem& e2)
{
return cmp(e2)>0;
}
int operator >= (elem& e2)
{
return cmp(e2)>=0;
}
Structuri de date (n baza C++): Suport de curs S.Pereteatcu, A.Pereteatcu
6
int operator < (elem& e2)
{
return cmp(e2)
Structuri de date (n baza C++): Suport de curs S.Pereteatcu, A.Pereteatcu
7
double salary;
public:
usual_elem()
{
name[0]='\0';
year=0;
salary=0.0;
}
usual_elem(char* init_name, int init_year, double init_salary)
{
strcpy(name, init_name);
year=init_year;
salary=init_salary;
}
virtual int fscanf_el(FILE *f)
{
return fscanf(f, "%s %d %lf", name, &year, &salary);
}
virtual void show(const char* opening=NULL,
const char* ending=NULL)
{
if(!opening)
opening="";
if(!ending)
ending="\n";
cout
Structuri de date (n baza C++): Suport de curs S.Pereteatcu, A.Pereteatcu
8
return strcmp(this->name, ((usual_elem&)e2).name);
}
};
Crem un fiier text cu numele, de exemplu, stud.txt, din care mai departe vom introduce informaii pentru ncrcarea diferitelor structuri de date. Coninutul fiierului stud.txt va arta astfel: Green 1987 350.00
Red 1980 450.00
Blue 1981 500.00
Gray 1968 900.00
Orange 1984 550.00
White 1980 600.00
Cyan 1975 800.00
Yellow 1988 300.00
Magenta 1983 600.00
Black 1981 500.00
In fine, declarm clasa abstract SD, care va servi n viitor ca clasa de baz pentru declararea diferitelor claselor de reprezentare a structurilor de date. //
// a b s t r a c t c l a s s "S D"
//
class SD
{
protected:
FILE* pf;
long ncomp;
public:
SD()
{
pf=NULL;
ncomp=0;
}
SD(char* file_name)
{
if(!(pf=fopen(file_name, "rt")))
{
char *mes = new char[5+strlen(file_name)+12+1];
error(strcat(strcat(strcpy(mes,"File "),file_name),
" not found!\n"));
Structuri de date (n baza C++): Suport de curs S.Pereteatcu, A.Pereteatcu
9
}
ncomp=0;
}
~SD()
{
if(pf)
fclose(pf);
}
virtual void show(const char* opening=NULL,
const char* ending=NULL)=0;
long get_ncomp()
{
return ncomp;
}
void reset_ncomp()
{
ncomp=0;
}
protected:
void error(char* message)
{
cerr
Structuri de date (n baza C++): Suport de curs S.Pereteatcu, A.Pereteatcu
10
2. TABELE
2.1. Noiune de tabel
Tabel este un set de elemente, fiecare din care are un indicator special numit
cheie cu proprietatea c elementele se adaug n tabel i se caut n tabel dup cheie. Pe lng cheie, elementul din tabel (se mai numete nc nregistrare
tabelar) de obicei conine date, purttoare de careva informaii.
Exemplul 1.
Tabelul ptratelor numerelor naturale Cheia
(valoarea
argumentului)
Datele
(valoarea
funciei)
0 0
1 1
2 4
3 9
4 16
5 25
6 36
Cheia n acest tabel este valoarea argumentului, dar valoarea funciei reprezint informaii.
Exemplul 2.
Tabelul de trecere din baza 10 n bazele 2, 8 i 16 Datele Cheia
(valoarea
numrului
n baza 10)
Valoarea
numrului
n baza 2
Valoarea
numrului
n baza 8
Valoarea
numrului
n baza 16
0 0000 00 0
1 0001 01 1
2 0010 02 2
3 0011 03 3
4 0100 04 4
5 0101 05 5
6 0110 06 6
7 0111 07 7
8 1000 10 8
9 1001 11 9
Structuri de date (n baza C++): Suport de curs S.Pereteatcu, A.Pereteatcu
11
10 1010 12 A
11 1011 13 B
12 1100 14 C
13 1101 15 D
14 1110 16 E
15 1111 17 F
Cheia n acest tabel este valoarea numrului n baza 10, iar datele poart informaii despre valoarea numrului n bazele 2, 8 i 16.
Exemplul 3:
Tabelul de nume simbolice Datele Cheia
Symbol name Type Value
!!DATE Text 09/15/12
??FILENAME Text sumvectr
??TIME Text 11:28:21
A10 Near COD:004E
B10 Near COD:00AD
BINSTR Near COD:01A0
C10 Near COD:0105
N Word DATE:0067
NOMBIN Word DATE:02CF
S10 Near COD:0181
Z Byte DATE:0061
ZMAX Byte DATE:005F
ZT Word DATE01F9
Compilatoare i interpretatoare folosesc tabele de nume. Cheia n astfel de tabel este identificatorul, dar datele poart informaii despre tipul variabilei, adresa de alocare n memoria calculatorului, etc.
n memoria calculatorului tabele de obicei sunt prezentate sub form de vectori de nregistrri, dar uneori se folosesc i liste, sau combinri dintre vectori i liste.
Referitor la tabele o problem cea mai important este problema de cutare.
Problema cutrii const n aflarea dup cheia dat adresei (locului) de pstrare
a nregistrrii tabelare cu aa cheie, sau ajungerea la concluzie c o aa
nregistrare nu este n tabel.
Aceast problem se rezolv diferit, n dependen de metoda organizrii a tabelului.
Caracteristica principal a metodei de organizare a tabelului este timpul mediu de cutare a unei nregistrri tabelare. Acest timp este proporional lungimii medii de cutare.
Structuri de date (n baza C++): Suport de curs S.Pereteatcu, A.Pereteatcu
12
Lungimea medie de cutare este numrul mediu de nregistrri parcurse pentru
cutarea nregistrrii necesare.
2.2. Tabele neordonate
n tabele neordonate nregistrrile sunt aranjate una dup alta (pe msura venirii) fr lipsuri. Astfel de tabele uor se alctuiesc. O nou nregistrare pur i simplu se adaug la sfritul tabelului dup nregistrarea precedent.
Pentru cutare n aa tabele se aplic parcurgerea secvenial, prin care nregistrrile se parcurg la rnd una dup alta, ncepnd cu prima.
Lungimea medie de cutare prin parcurgerea secvenial a tabelului cu n nregistrri tabelare se calculeaz prin formula:
n
iiipD
1
(2.1)
unde i - este numrul de ordine a nregistrrii, iar pi probabilitatea c nregistrarea necesar are numr i.
Dac nregistrarea cutat se afl n orice loc al tabelului cu probabilitatea egal, atunci n
pi1
, i
lungimea medie de cutare va fi egal:
22
11
11
nnnnn
iD
n
i
(2.2)
Tabelele neordonate nu sunt economice dup timpul de cutare, de aceea ele nu se folosesc n calitate de tabele constante n translatoare (compilatoare sau interpretatoare). ns adugarea unei nregistrri noi n aa tabele necesit timpul minim, deaceea tabelele neordonate uneori se folosesc n translatoare ca tabele temporare, ncrcndu-se n timpul translaiei. La nceputul vectorului de reprezentare a acestui tabel, deseori se pstreaz numrul maximal posibil de nregistrri i numrul primei linii libere din tabel.
Pentru a demonstra lucrul cu tabele neordonate declarm clasa table, ca o clas generic ce depinde de un tip parametrizat reprezentnd o nregistrare tabelar. //
// c l a s s "t a b l e"
//
const NMAX=200;
//
template class table : public SD {
protected:
int n; // numrul de nregistrri tabelare
Structuri de date (n baza C++): Suport de curs S.Pereteatcu, A.Pereteatcu
13
el t[NMAX]; // vector de nregistrri tabelare
public:
table()
{
n=0;
}
table(char* file_name) :
SD(file_name)
{
int repeated;
n=0;
while(!feof(pf))
if(t[n].fscanf_el(pf)>0)
{
if ( (repeated=search(t[n]))>=0 )
{
char message[60];
char repeated_str[10];
message[0]='\0';
strcat(message,
"Key coincides with the key in the position: ");
strcat(message, itoa(repeated+1, repeated_str, 10));
strcat(message, "!\n");
error(message);
}
n++;
}
fclose(pf) , pf=NULL; }
virtual void show(const char* opening =NULL, const char* ending=NULL)
{
clrscr();
cout
Structuri de date (n baza C++): Suport de curs S.Pereteatcu, A.Pereteatcu
14
{
if(i>0 && i%20==0)
{
cout
Structuri de date (n baza C++): Suport de curs S.Pereteatcu, A.Pereteatcu
15
cin >> surname;
usual_elem e(surname, 2000, 0.0);
gr.reset_ncomp();
int pos=gr.search(e);
if(pos
Structuri de date (n baza C++): Suport de curs S.Pereteatcu, A.Pereteatcu
16
n urmtorul exemplu al funciei main() se calculeaz lungimea medie de cutare pentru un tabel simplu neordonat creat n baza fiierului stud.txt. void main()
{
clrscr();
table gr("Stud.txt");
gr.show("Group:\n","");
usual_elem sample;
long NCOMP=0;
FILE* pf=fopen("Stud.txt", "rt");
while(!feof(pf))
if(sample.fscanf_el(pf)>0)
{
gr.reset_ncomp();
if(gr.search(sample)>=0)
NCOMP+=gr.get_ncomp();
}
fclose(pf);
cout
Structuri de date (n baza C++): Suport de curs S.Pereteatcu, A.Pereteatcu
17
2.3. Tabele neordonate structurate arborescent
Cteodat n calitate de tabele temporare se aplic tabele neordonate structurate arborescent, organizate n form de arbore binar. La fiecare nregistrare tabelar n aa tabele se adaug cte doi pointeri: un pointer spre nregistrarea tabelar cu valoarea mai mic a cheii, iar al doilea pointer spre nregistrrea tabelar cu valoarea mai mare a cheii.
O nou nregistrare se adaug n tabel la rnd, ca i n tabele neordonate simple. Dup adugarea n tabel a noii nregistrri valoarea cheii se compar cu valoarea cheii a primei nregistrri a tabelului. Dup rezultatul comparrii cu ajutorul pointerilor se afl adresa pstrrii urmtoarei nregistrri, cu cheia crei trebuie de comparat valoarea cheii nregistrrii noi. Acest proces are loc pn atunci, pn cnd nu va fi gsit nregistrarea tabelar cu pointerul vid n direcia necesar de cutare. n acest pointer se nscrie adresa pstrrii noii nregistrri tabelare.
De exemplu, n figura 2.1 este artat tabelul neordonat structurat arborescent creat pe baza fiierului Stud.txt.
Pentru a demonstra lucrul cu tabele neordonate structurate arborescent mai nti de toate crem n baza clasei usual_elem clasa tree_like la care mai adaugm dou cmpuri cu caracter de pointeri. //
// c l a s s "t r e e l i k e" e l e m e n t s
//
class tree_like: public usual_elem
{
protected:
int less;
int greater;
public:
tree_like()
{
less=greater=-1;
}
tree_like(char* init_name, int init_year, double init_salary):
usual_elem(init_name, init_year, init_salary)
{
less=greater=-1;
}
int get_less()
{
return less;
}
Structuri de date (n baza C++): Suport de curs S.Pereteatcu, A.Pereteatcu
18
int set_less(int new_less)
{
return less=new_less;
}
int get_greater()
Fig. 2.1 Tabelul neordonat structurat arborescent
00
01 Red 1980, 450
4 5
02 Blue 1981, 500
9 3
03
04 Orange
05
1984, 550
8 -1
White 1980, 600
-1 7
06 Cyan 1975, 800
-1 -1
07 Yellow 1988, 300
-1 -1
08
09
Magenta 1983, 600
-1 -1
Black 1981, 500
-1 -1
Gray 1968, 900
6 -1
Green 1987, 350
2 1
Structuri de date (n baza C++): Suport de curs S.Pereteatcu, A.Pereteatcu
19
{
return greater;
}
int set_greater(int new_greater)
{
return greater=new_greater;
}
virtual void tree_show(const char* opening =NULL, const char* ending=NULL)
{
if(!opening)
opening="";
if(!ending)
ending="\n";
cout
Structuri de date (n baza C++): Suport de curs S.Pereteatcu, A.Pereteatcu
20
for(int i=1; i
Structuri de date (n baza C++): Suport de curs S.Pereteatcu, A.Pereteatcu
21
}
int search(el e)
{
int position = -1;
int forward=1;
int i=0;
int cmp_result;
while(forward)
if( ncomp++, (cmp_result=e.cmp(t[i]))==0 )
position=i, forward=0;
else
{
if(cmp_result
Structuri de date (n baza C++): Suport de curs S.Pereteatcu, A.Pereteatcu
22
char ch='n';
char surname[21];
while(ch!='y')
{
cout > surname;
tree_like e(surname, 2000, 0.0);
tree_gr.reset_ncomp();
int pos=tree_gr.search(e);
if(pos
Structuri de date (n baza C++): Suport de curs S.Pereteatcu, A.Pereteatcu
23
5. Orange, 1984, 550 [8, -1]
6. White, 1980, 600 [-1, 7]
7. Cyan, 1975, 800 [-1, -1]
8. Yellow, 1988, 300 [-1, -1]
9. Magenta, 1983, 600 [-1, -1]
10. Black, 1981, 500 [-1, -1]
End of Table. Press any key ...
Enter a name to search: White
There are in the position 6. The number of comparisons: 3
Done ? (y/n)
Enter a name to search: Green
There are in the position 1. The number of comparisons: 1
Done ? (y/n)
Enter a name to search: Black
There are in the position 10. The number of comparisons: 3
Done ? (y/n)
Enter a name to search: Purple
No table! The number of comparisons: 3
Done ? (y/n)
Dac vrem s calculm lungimea medie de cutare pentru acest tabel, scriem funcia main() astfel: void main()
{
clrscr();
tree_table gr("stud.txt");
gr.tree_show("Group:\n","");
tree_like sample;
long NCOMP=0;
FILE* pf=fopen("stud.txt", "rt");
while(!feof(pf))
if(sample.fscanf_el(pf)>0)
{
gr.reset_ncomp();
if(gr.search(sample)>=0)
NCOMP+=gr.get_ncomp();
}
fclose(pf);
cout
Structuri de date (n baza C++): Suport de curs S.Pereteatcu, A.Pereteatcu
24
}
Afiarea va arta: Group:
1. Green, 1987, 350 [2, 1]
2. Red, 1980, 450 [4, 5]
3. Blue, 1981, 500 [9, 3]
4. Gray, 1968, 900 [6, -1]
5. Orange, 1984, 550 [8, -1]
6. White, 1980, 600 [-1, 7]
7. Cyan, 1975, 800 [-1, -1]
8. Yellow, 1988, 300 [-1, -1]
9. Magenta, 1983, 600 [-1, -1]
10. Black, 1981, 500 [-1, -1]
End of Table. Press any key ...
N=10, NCOMP=29, ALS=2.9, MAX=5, MIN=5.32193
Analiza rezultatelor rmne ca exerciiu.
Neajunsul tabelelor neordonate structurate arborescent cheltuieli mai mari de memorie (pentru pstrarea pointerilor) i algoritmii de ncrcare tabelului i cutare nregistrrilor puin mai complicai n comparaie cu cei pentru tabelele neordonate simple.
2.4. Tabele ordonate
Tabele pot fi ordonate cresctor dup codul numeric al cheii, sau dup frecvena apelurilor la nregistrri. n primul caz pentru cutarea nregistrrii de obicei se folosete cutarea binar, dar n al doilea parcurgerea secvenial.
Cutarea binar const n mprirea tabelului n dou pri aproape egale i constatarea n care din cele dou pri se gsete valoarea cheii cutat. Partea ce conine cheia se supune de fiecare dat mpririi secveniale. Fiindc tabelul este aranjat cresctor dup cheie, pentru a gsi n care parte se afl valoarea cheii cutate, valoarea cheii n punctul mpririi se compar cu valoarea cheii cutate. //
// c l a s s "s o r t e d t a b l e"
//
template class sorted_table: public table
{
public:
sorted_table()
{
}
Structuri de date (n baza C++): Suport de curs S.Pereteatcu, A.Pereteatcu
25
sorted_table(char* file_name)
{
el tmp;
pf=fopen(file_name, "rt");
n=0;
while(!feof(pf))
if(tmp.fscanf_el(pf)>0)
{
int i;
for(i=n-1; i>=0 && (tmp0 && i>=0 && tmp==t[i])
{
char message[60];
char repeated_str[10];
message[0]='\0';
strcat(message,
"Key coincides with the key in the position: ");
strcat(message, itoa(i+1, repeated_str, 10));
strcat(message, "!\n");
error(message);
}
t[i+1]=tmp, n++;
}
fclose(pf) , pf=NULL; }
int search(el e)
{
int a=0, b=n-1;
int result;
while(a0)
a=i+1;
else
if(result
Structuri de date (n baza C++): Suport de curs S.Pereteatcu, A.Pereteatcu
26
}
return (ncomp++, e==t[a])? a : -1;
}
};
n funcia main() demonstrm utilizarea tabelelor sortate dup cheie. void main()
{
clrscr();
sorted_table sorted_gr("stud.txt");
sorted_gr.show("Group:\n","");
char ch='n';
char surname[21];
while(ch!='y')
{
cout > surname;
usual_elem e(surname, 2000, 0.0);
int pos=sorted_gr.search(e);
int pos=sorted_gr.search(e);
if(pos
Structuri de date (n baza C++): Suport de curs S.Pereteatcu, A.Pereteatcu
27
7. Orange, 1984, 550
8. Red, 1980, 450
9. White, 1980, 600
10. Yellow, 1988, 300
End of Table. Press any key ...
Enter a name to search: White
There are in the position 9. The number of comparisons: 4
Done ? (y/n)
Enter a name to search: Green
There are in the position 5. The number of comparisons: 2
Done ? (y/n)
Enter a name to search: Black
There are in the position 1. The number of comparisons: 5
Done ? (y/n)
Enter a name to search: Purple
No table! The number of comparisons: 4
Done ? (y/n)
Lungimea cutrii binare se obine dup formula
2log 22 nD (2.3),
ce pentru n destul de mare aproape c este egal cu limita de jos teoretic pentru metode de cutare, bazate numai pe compararea cheilor. Teoretic limita de jos este egal cu log2(n+1). Cutarea binar mult mai efectiv dect parcurgerea secvenial. Pentru n=1000, D1=500, iar D2=11.
Pentru a calcula lungimea medie practic de cutare n tabelul ordonat creat n baza fiierului "stud.txt" modificm funcia main(). void main()
{
clrscr();
sorted_table gr("stud.txt");
gr.show("Group:\n","");
usual_elem sample;
long NCOMP=0;
FILE* pf=fopen("Stud.txt", "rt");
while(!feof(pf))
if(sample.fscanf_el(pf)>0)
{
gr.reset_ncomp();
if(gr.search(sample)>=0)
NCOMP+=gr.get_ncomp();
}
Structuri de date (n baza C++): Suport de curs S.Pereteatcu, A.Pereteatcu
28
fclose(pf);
cout
Structuri de date (n baza C++): Suport de curs S.Pereteatcu, A.Pereteatcu
29
2.5. Tabele cu adresare direct
Fie n tabel de m nregistrri, toate nregistrrile au diferite valori ale cheilor k0, k1, k2,..., km-1, i tabelul este reflectat n vectorul T[0], T[1], , T[n-1], unde mn. Dac este definit funcia f(k), astfel, ca pentru orice ki, i=0, ..., m-1, f(ki) are o valoare ntreag ntre 0 i n-1, unde f(ki)f(kj), ij atunci nregistrarea tabelar cu cheia K se reflect bireciproc n elementul T[f(K)].
Funcia f(K) se numete funcie de repartizare (dispersare sau Hash funcie). Aceast funcie asigur calcularea pentru fiecare nregistrare tabelar a numrului corespunztor al elementului vectorului T. Accesul la nregistrare dup cheia K se efectueaz n acest caz nemijlocit prin calcularea valorii f(K). Tabelele, pentru care exist i este cunoscut (descris) funcia de repartizare, se numesc tabele cu adresare direct. Lungimea medie de cutare n astfel de tabele este minimal i egal D3=1.
Alegerea funciei de repartizare, care asigur transformarea bireciproc a cheii nregistrrii n adresa de pstrare, n caz general este o problem destul de complicat. Practic ea poate fi rezolvat numai pentru tabelele constante cu setul de valori pentru cheii tiut dinainte. De exemplu: tabelul de recodificare, tabelul de simboluri ale limbajului de intrare al translatorului.
2.6. Tabele de repartizare (repartizarea aleatorie)
Noiuni generale
Deoarece, practic transformarea bireciproc a cheii n adresa pstrrii nregistrrii, n mod general, nu poate fi ndeplinit, atunci suntem nevoii s ne refuzm de cerin de reflectare birereciproc. Aceasta aduce la suprapunerea nregistrrilor sau, altfel zis, la coliziuni. Ca astfel de coliziuni s fie ct mai puine, funcia de repartizare se alege din condiia de reprezentare aleatorie i cu ct se poate mai uniform de reflectarea cheilor n adresa de pstrare. Tabele construite dup acest principiu sunt numite tabele de repartizare.
Repartizarea nu exclude pe deplin posibilitatea de suprapunere a nregistrrilor (coliziuni). De acea se aplic diferite metode pentru nlturarea coliziunilor. Diferena variantelor de tabele de repartizare este definit prin metoda folosit de nlturare a coliziunilor.
Tabele de repartizare cu examinarea liniar (adresare deschis)
n metoda de repartizare cu examinarea liniar la reprezentarea tabelelor n vector de lungime n se folosete urmtorul algoritm al inserrii nregistrrii cu cheia dat K:
1. Calculm i=f(K). Trecem la punctul 2. 2. Dac poziia i este liber, atunci nscriem n aceasta poziie nregistrarea noua. n caz contrar
trecem la punctul 3.
3. Punem i=(i+1) mod n, i trecem la punctul 2:
nidaca
nidacaii
1,0
1,1
La includerea unei noi nregistrri algoritmul rmne determinat pn atunci, cnd vectorul, n care se reflect tabelul, conine mcar o poziie liber.
Structuri de date (n baza C++): Suport de curs S.Pereteatcu, A.Pereteatcu
30
Dac aceast condiie nu se ndeplinete este posibil ciclarea, mpotriva creia trebuie de luat msuri speciale. De exemplu, se poate introduce un contor de poziii verificate, dac acest numr a devenit mai mare ca n, atunci algoritmul trebuie s fie oprit.
La cutarea nregistrrii cu cheia dat K se folosete urmtorul algoritm:
1. Calculm i=f(K). Trecem la punctul 2
2. Dac poziia i este liber atunci n tabelul dat nu exist nregistrarea cu cheia K. Dac poziia este ocupat i cheia coincide cu cheia K, atunci cutarea este reuit, n caz contrar trecem la punctul 3.
3. Punem i=(i+1) mod n, i trecem la punctul 2:
nidaca
nidacaii
1,0
1,1
La cutare algoritmul este determinat dac tabelul conine nregistrarea tabelar cu cheia K, sau vectorul conine poziii libere. n cazul nendeplinirii acestor condiii trebuie de luat msuri speciale. De exemplu, se poate introduce un contor de poziii verificate, dac acest numr a devenit mai mare ca n, atunci algoritmul trebuie s fie oprit.
Declarm n baza clasei usual_elem clasa hashing_elem care va fi dotat cu o funcie de repartizare. //
// c l a s s "h a s h i n g _ e l e m"
//
class hashing_elem : public usual_elem
{
public:
hashing_elem()
{
}
hashing_elem(char* init_name, int init_year, double init_salary):
usual_elem(init_name, init_year, init_salary)
{
}
int hf(int n) // hashing function
{
return (name[0]-'A')%n;
}
};
n exemplul acesta valoarea funciei de dispersare este egal cu numrul de ordine al primei litere a numelui n alfabet. Numrul de ordin se moduleaz dup mrimea vectorului de reprezentare.
Structuri de date (n baza C++): Suport de curs S.Pereteatcu, A.Pereteatcu
31
n baza clasei generice table declarm clasa hashing_table tot generic, care asigur lucrul cu tabele de repartizare cu examinarea linear. //
// c l a s s "h a s h i n g t a b l e"
//
template class hashing_table: public table
{
protected:
int m;
public:
hashing_table(char* file_name, int n_init)
{
n=n_init, m=0;
el tmp;
int repeated;
pf=fopen(file_name, "rt");
m=0;
while(!feof(pf))
if(tmp.fscanf_el(pf)>0)
{
int i=tmp.hf(n);
repeated=-1;
while((repeated==-1) && !t[i].free())
{
if ( tmp==t[i] )
repeated=i;
else
i=(i+1)%n;
}
if ( repeated!=-1 )
{
char message[60];
char repeated_str[10];
message[0]='\0';
strcat(message,
"Key coincides with the key in the position: ");
strcat(message, itoa(repeated+1, repeated_str, 10));
strcat(message, "!\n");
error(message);
}
t[i]=tmp;
Structuri de date (n baza C++): Suport de curs S.Pereteatcu, A.Pereteatcu
32
m++;
}
fclose(pf), pf=NULL;
}
int search(el e)
{
int position=-1;
int i=e.hf(n);
while((position==-1) && !t[i].free())
if(ncomp++, e==t[i])
position=i;
else
i=(i+1)%n;
return position;
}
int get_m()
{
return m;
}
};
n funcia main()crem un tabel de repartizare cu examinarea linear, ncrcnd acest tabel din fiierul text Stud.txt. Apoi afim acest tabel i cutm careva nregistrri dup cheie. void main()
{
clrscr();
hashing_table hashing_gr("stud.txt", 15);
hashing_gr.show("Group:\n","");
char ch='n';
char surname[21];
while(ch!='y')
{
cout > surname;
hashing_elem e(surname, 2000, 0.0);
hashing_gr.reset_ncomp();
int pos=hashing_gr.search(e);
if(pos
Structuri de date (n baza C++): Suport de curs S.Pereteatcu, A.Pereteatcu
33
else
cout
Structuri de date (n baza C++): Suport de curs S.Pereteatcu, A.Pereteatcu
34
Pentru exemplul nostru tabelul va arta astfel:
Dup cum se vede poziiile 0, 5, 10, 11, 13 au rmas libere. Pe parcursul completrii tabelului n poziiile 1, 2, 6, 7 au avut loc coliziuni. Drept vorbind, coliziunea n poziia 7 pentru nregistrarea tabelar cu cheia White este secundar.
Cercetrile teoretice i experimente pentru cutarea la metoda de repartizare cu examinarea liniar au artat, c pentru repartizarea aleatorie i uniform a nregistrrilor prin funcia de repartizare n intervalul [0, n-1], lungimea medie de cutare nu depinde de lungimea tabelului, dar depinde numai
de factorul de ncrcare nm
, unde m - lungimea tabelului, iar n lungimea vectorului de
reprezentare.
Aceast proprietate este foarte important, mai ales pentru tabele mari. Tabele deterministe, att aranjate ct i cele nearanjate nu posed aceast proprietate. n tabele deterministe lungimea medie de cutare crete cu creterea lungimii tabelului.
Formula aproximativ
22
2)(
D , pentru lungimea medie de cutare la metoda de repartizare
cu examinarea liniar ofer coinciden suficient cu experimentul pentru 0,85.
Formula este obinut n presupunerea repartizrii aleatorie i uniform a nregistrrilor pe poziiile vectorului de reprezentare.
Urmtorul tabel demonstreaz dependena lungimii medie de cutare de factorul de ncrcare .
0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9
D() 1.06 1.13 1.21 1.33 1.50 1.75 2.17 3.00 5.5
02 Red, 1980, 450
03 Cyan, 1975, 800
04 Black, 1981, 500
05
07 Gray, 1968, 900
08 White, 1980, 600
09 Yellow, 1988, 300
10
11
13
14 Orange, 1984, 550
00
06 Green, 1987, 350
12 Magenta,1983, 600
01 Blue, 1981, 500
Green
Red
Blue
Gray
Orange
White
Cyan Yellow
Magenta
Black
Structuri de date (n baza C++): Suport de curs S.Pereteatcu, A.Pereteatcu
35
Experimentele arat, c pentru =1 lungimea medie de cutare nu ntrece 20.
Dac distribuirea nregistrrilor pe poziiile vectorului de reflectare nu este uniform, atunci numerele din tabel cresc n mediu cu 1.5 2 ori. Chiar i cu astfel de corecii repartizarea cu examinarea linear are lungimea medie de cutare mai mic, ca alte metode. De exemplu, pentru tabelul din 400 nregistrri i lungimea vectorului de reflectare 512, lungimea medie de cutare pentru tabelul de repartizare cu examinarea liniar, lund n consideraie distribuirea neuniform a nregistrrilor, nu depete 4.5 6. n aceleai condiii lungimea medie la cutarea binar este egal cu 10, iar lungimea medie a parcurgerii secveniale 200.
Neajunsurile: la repartizarea cu examinarea liniar aproape 20% de memorie, rezervat pentru tabel, nu se folosete.
Pentru a calcula lungimea medie de cutare pentru tabelul cu repartizare linear din exemplul nostru, cercetm urmtoarea funcia main(): void main()
{
clrscr();
hashing_table hashing_gr("stud.txt", 15);
hashing_gr.show("Group:\n","");
hashing_elem sample;
long NCOMP=0;
FILE* pf=fopen("stud.txt", "rt");
while(!feof(pf))
if(sample.fscanf_el(pf)>0)
{
hashing_gr.reset_ncomp();
if(hashing_gr.search(sample)>=0)
NCOMP+=hashing_gr.get_ncomp();
}
fclose(pf);
cout
Structuri de date (n baza C++): Suport de curs S.Pereteatcu, A.Pereteatcu
36
2. Blue, 1981, 500
3. Red, 1980, 450
4. Cyan, 1975, 800
5. Black, 1981, 500
6.
7. Green, 1987, 350
8. Gray, 1968, 900
9. White, 1980, 600
10. Yellow, 1988, 300
11.
12.
13. Magenta, 1983, 600
14.
15. Orange, 1984, 550
End of Table. Press any key ...
M=10, NCOMP=16, ALS=1.6, m/n=0.666667, D(m/n)=2
Analiza rezultatelor rmne ca exerciiu.
Tabele de repartizare cu nlnuirea extern (repartizarea deschis, nlnuirea separat)
n metoda examinrii liniare nregistrrile ce produc coliziuni se includ n poziiile libere aceluiai vector de reflectare. ns pentru aceste nregistrri se poate crea un tabel aparte. n tabelul adugtor nregistrrile se poate lega n lan, ca n liste, pentru uurarea cutrii.
n tabele de repartizare cu nlnuirea extern lungimea medie de cutare pentru distribuirea
uniform i aleatorie a nregistrrilor se definete dup formula:
n
mnmD
21
1,
, n lungimea vectorului de reflectare, m lungimea tabelului.
Structuri de date (n baza C++): Suport de curs S.Pereteatcu, A.Pereteatcu
37
Tabele de repartizare cu nlnuirea intern
ncrcarea poziiilor vectorului de reflectare const din dou etape:
prima etap se aseamn cu repartizarea cu nlnuirea extern;
a doua etap se ndeplinete dup terminarea crerii tabelului primar i celui secundar. Ea const n mutarea lanurilor din tabelul secundarr n poziiile libere ale tabelului primar.
Astfel tabelele din exemplul precedent vor fi transformate n urmtorul tabel:
Prioritatea acestei metode n comparaie cu precedenta economie de memorie, dar neajunsul flexibilitatea mic i algoritmul de ncrcare a tabelului este mai complicat.
Lungimea medie de cutare aici se definete dup aceiai formula: n
mnmD
21
1),(
, aceast
metod se folosete pentru tabele permanente, i pentru tabele temporare, care se ncrc la prima etap, dar se folosesc la alta.
03
04
05
08
10
11
13
00
03 04 05
07 08 09 10 11
13 14
00|Gray, 1968,900
06
12
Primary Table
Secondary Table
Gray 06Green, 1987,35000
Green
14Orange,1984,550
Orange 07White, 1980,600
White
Cyan
02Red, 1980,45001
Red
09Yellow,1988,300 Yellow
12Magenta,1983,600
Magenta
01Cyan, 1975,800 02Black, 1981,500|
Black
01Blue, 1981,50002
Blue
Structuri de date (n baza C++): Suport de curs S.Pereteatcu, A.Pereteatcu
38
Pentru tabele constante nregistrrile cel mai des folosite se nscriu primele, atunci accesrile
lanurilor interioare sunt rare, ce micoreaz lungimea medie de cutare. Este caracter, c la folosirea lanurilor interioare toate poziiile ale vectorului de reflectare pot fi ncrcate (adic m=n), dar lungimea medie de cutare pentru repartizarea uniform i aleatorie a nregistrrilor nu ntrece 1.5.
Tabelele de repartizare aleatorie se ncarc destul de simplu, nu necesit ordonarea nregistrrilor i asigur o cutare rapid. Deaceea aceste tabele deseori se folosesc n practic.
Funcii de repartizare
Timpul calculrii funciei de repartizare f(k) intr n timpul mediu de cutare, deaceiea trebuie de inut cont la alegerea algoritmului, realiznd funcia de repartizare.
O funcie bun de repartizare trebuie s asigure repartizarea uniform a nregistrrilor pe poziiile vectorului de reflectare, fiindc distribuirea neuniform mrete timpul mediu de cutare. ns dac calcularea valorii funciei de repartizare necesit ndeplinirea unui numr mare de operaii, aceasta poate distruge toat economia n timpul cutrii. Deci, algoritmul calculrii funciei de repartizare nu trebuie s fie complicat. S privim cteva metode de calculare a funciei de repartizare:
1. Una din metodele simple se bazeaz pe evidenierea unei pri din codul numeric al cheii. De exemplu, fie dimensiunea maxim ateptat a tabelului de nume simbolice nu ntrece 256. Atunci funcia de repartizare poate avea n calitate de valoare 8 bii, fiindc 256=28. Se poate pur i simplu de a evidenia primii 8 bii din codul binar al identificatorului sau de a lua careva 8 bii din mijlocul codului. Trebuie doar s asigurm cu ct este posibil o distribuire uniform a nregistrrilor prin funcia f(k) n intervalul [0, 255].
05
08
10
11
13
04Gray, 1968,900
Gray 06Green, 1987,35004
Green
14Orange,1984,550
Orange 07White, 1980,600
White
09Yellow,1988,300 Yellow
12Magenta,1983,600
Magenta
00Black, 1981,500
Black
01Blue, 1981,50000
Blue
03Cyan, 1975,800
Cyan
02Red, 1980,45003
Red
Structuri de date (n baza C++): Suport de curs S.Pereteatcu, A.Pereteatcu
39
2. Pentru asigurarea distribuirii uniforme se folosete sumarea codului identificatorului: prima jumtate a codului se sumeaz cu a doua i din rezultat se evideniaz 8 bii. Se poate de asemenea de mprit codul cheii n buci cte 8 bii, de sumat bucile i de pus suma pe modulul 28. Ultima modificare are careva probabilitate teoretic: la presupunerea a statisticei independente de sumare a bucilor se primete repartizarea aproape de uniform.
3. O alt metod de calculare a funciei de repartizare este mprirea. Pentru vectorul de reflectare de lungimea n, cheia se privete ca un numr ntreg i se mparte la mrimea n. Experimentele arat, c restul de la mprire este repartizat aproape uniform n intervalul [0, n-1] i poate fi folosit ca valoarea funciei de repartizare.
Verificarea experimental a metodelor descrise pentru tabelele de repartizare cu examinarea linear a artat c evidenierea simpl a bucii din codul identificatorului mrete lungimea medie de
cutare n comparaie cu cea teoretic, definit dup formula:
22
2)(
D , n 4-5 sau i mai
multe ori. Lungimea medie de cutare pentru metoda de sumare a bucilor dup modulul 2k aproape de dou ori mai mare ca teoretic, dar pentru mprirea, lungimea medie de cutare practic coincide cu teoretic pentru 8.85.
Structuri de date (n baza C++): Suport de curs S.Pereteatcu, A.Pereteatcu
40
3. TEHNICI DE SORTARE
3.1. Noiuni generale
Sortarea este operaia de aranjare a elementelor unui vector dup valoarea
cheilor, pentru care este definit relaia de ordine.
Tradiional difer sortarea intern de sortarea extern. Sortarea intern prelucreaz datele pstrate n memoria operativ a calculatorului, dar sortarea extern, opereaz cu datele care sunt pstrate n fiiere.
n cazul sortrii interne se tinde la minimizarea numrului de comparaii i permutri ale elementelor.
n cazul sortrii externe factorul hotrtor este numrul de operaii de intrare i ieire. n acest caz numrul de comparaii trece pe planul doi, totui i el se i-a n consideraie.
Cazul sortrii interne
Presupunem, c datele supuse sortrii se pstreaz n memoria operativ ntr-un vector t. Fiecare element t[i] al acetui vector este obiect al clasei parametrizate el n care sunt suprancrcai operatorii de comparaie. Deci, sunt admise expresii:
t[i]
Structuri de date (n baza C++): Suport de curs S.Pereteatcu, A.Pereteatcu
41
Definiia 4. Algoritmul sortrii se numete stabil, dac el niciodat nu schimb
ordinea relativ n vector la oricare 2 elemente cu cheile egale. Adic pentru orice pereche i, j: ii', j>j' => i'
Structuri de date (n baza C++): Suport de curs S.Pereteatcu, A.Pereteatcu
42
{
protected:
int n; // numrul de elemente ale vectorului
el t[NMAX]; // elemente ale vectorului
long ncomp; // contorul comparaiilor
public:
vector()
{
n=0, ncomp=0;;
}
vector(char* file_name)
{
FILE* pf;
pf=fopen(file_name, "rt");
n=0, ncomp=0;
while(!feof(pf))
if(t[n].fscanf_el(pf)>0)
n++;
fclose(pf);
}
virtual void show(const char* opening, const char* ending)
{
clrscr();
cout
Structuri de date (n baza C++): Suport de curs S.Pereteatcu, A.Pereteatcu
43
int search(el e)
{
int position = -1;
for(int i=0; (position==-1) && it[i])
position=i;
return position;
}
int get_n()
{
return n;
}
long get_ncomp()
{
return ncomp;
}
void reset_ncomp()
{
ncomp=0;
}
protected:
void error(char* message)
{
cerr
Structuri de date (n baza C++): Suport de curs S.Pereteatcu, A.Pereteatcu
44
3.3. Sortarea prin interschimbare
Metoda de sortare prin interschimbare (engl. Exchange sort) const n parcurgerea elementelor ale vectorului, n aa mod ca fiecare parcurgere micoreaz numrul de inversii, pn atunci cnd nu rmne nici o inversie. Problema const n cutarea urmtoarei inversiei (i, j).
Schematic: while (este_inversie (i, j))
swap(i, j);
Sortarea prin interschimbare const n modificri succesive de tip t[i]t[j], pn cnd elementele vectorului nu vor deveni n ordine cresctoare.
Din aceast categorie fac parte metoda bulelor (bubblesort) unul din cei mai slabi algoritmi de sortare i sortarea rapid (quicksort) unul din cei mai buni algoritmi de sortare.
Sortarea prin metoda bulelor
Metoda bulelor const n compararea t[i] cu t[i+1], dac ordinea este bun se compar t[i+1] cu t[i+2], dac ordinea nu este bun se interschimb t[i] cu t[i+1] i apoi se compar t[i+1] cu t[i+2]. Dup prima parcurgere a vectorului, pe ultima poziie ajunge elementul avnd valoarea cea mai mare, dup a doua parcurgere ajunge urmtorul element pe penultima poziie, etc.
Algoritmul are complexitatea O(n2).
void bubble_sort()
{
BOOLEAN inversion;
do
{
inversion = FALSE;
for(int i=0; it[i+1])
{
swap(i,i+1);
inversion = TRUE;
}
}
while (inversion);
}
Complexitatea minim este O(n). Dac vectorul iniial este deja sortat, variabila inversion niciodat nu va primi valoarea TRUE.
Complexitatea maxim este O((n-1)2)=O(n2). Dac elementul minimal are indicele iniial n-1, atunci va fi nevoie de n-1 executri a ciclului exterior, ca s-i dm indicele 0.
Pentru fiecare executare a ciclului exterior cu n-1 comparaii: (n-1)*(n-1)=(n-1)2 comparaii.
Structuri de date (n baza C++): Suport de curs S.Pereteatcu, A.Pereteatcu
45
Complexitatea medie de asemenea este egal cu O(n2), dac elementul minimal cutat se afl aleator printre indicii 0, 1,, n-1.
Exerciiu: Este posibil mbuntirea acestui algoritm, ce nu schimb totui esenial complexitatea. mbuntii algoritmul de mai sus, prescurtnd cu un element parcurgerea de rnd fa de precedent.
Metoda bulelor este unul din cei mai ri algoritmi de sortare. Neajunsul const n aceea c la fiecare pas elementul urmtor se compar numai cu vecinul su urmtor.
3.4. Sortarea rapid
Sortarea rapid (quicksort) a fost propus de C.A.R. Hoare i folosete principiile Divide Et Impera i Echilibru.
Ideea metodei este urmtoarea: se selecteaz un element arbitrar din vector numit principal (sau pivot) i se rearanjeaz vectorul n doi subvectori, astfel nct cel din stnga are toate elementele mai mici sau egale dect pivotul, iar cel din dreapta mai mari sau egale ca pivotul. Procedeul se reia n subvectorul din stnga i apoi n cel din dreapta, etc. Procedeul se termin cnd se ajunge la subvectori dintr-un singur element.
n baza clasei generice vector declarm clasa derivat vector_quicksort, dotat cu algoritmul de sortare rapid. //
// c l a s s " v e c t o r q u i c k s o r t"
//
template class vector_quicksort: public vector
{
public:
vector_quicksort(char* file_name):
vector(file_name)
{
}
void quicksort(int i=0, int j=-1)
{
if(j>=n || j==-1)
j=n-1;
if(ij)
i=0;
quicksort_intern(i, j);
}
protected:
void quicksort_intern(int i, int j);
int divide(int i, int j);
Structuri de date (n baza C++): Suport de curs S.Pereteatcu, A.Pereteatcu
46
};
Presupunem c exist funcia numit divide(), care ntr-un anumit fel alege elementul principal cu cheia K i rearanjeaz vectorul astfel, ca elementul principal primete un indice imain, iar toate elementele cu cheile K se aranjeaz de la stnga (adic au indicii < imain), dar toate elementele cu cheile K se aranjeaz de la dreapta (adic au indicii >imain):
Avem aici un caz tipic recursiv:
parametrizarea: se precaut pentru subvectorul t[i]t[j]; pentru vectorul iniial i=0, j=n-1;
cazul trivial: i=j (nu avem ce sorta);
trecerea de la cazul general la un caz mai simplu, care are loc datorit funciei divide().
Dac exist o astfel de funcie, atunci sortarea rapid imediat se obine n form recursiv: template
void vector_quicksort::quicksort_intern(int i, int j)
{
if (j>i)
{
int imain=divide(i,j);
quicksort_intern(i,imain-1);
quicksort_intern(imain+1,j);
}
}
Algoritmul are loc pentru ambele ordine de apeluri recursive.
Schema metodei de divizare n timpul O(n):12 3 15 10 2 20 4
principal
elementul
Prelucrm vectorul din stnga i din dreapta pn atunci, pn cnd din stnga nu va fi gsit elementul cu cheia, ce ntrece cheia elementului principal, dar din dreapta elementul cu cheia mai mic ca cheia elementului principal. Dup aceasta se poate de schimbat cu locurile aceste dou elemente, lichidnd prin asta inversia. Apoi astfel de prelucrare dubl, din stnga i din dreapta, continu cu poziiile deja gsite. Vectorul se socoate mprit, cnd poziiile din stnga i din dreapta se ntlnesc. Valoarea comun a lor notm prin imain.
imain 0 n-1
imain-1
elementul principal t[imain]
elemente t[imain] elemente t[imain]
imain+1
Structuri de date (n baza C++): Suport de curs S.Pereteatcu, A.Pereteatcu
47
Evident, c complexitatea divizrii nu ntrece O(n), sau mai bine spus O(j-i) cnd divizarea se aplic la subvectorul t[i]t[j].
Sfaturi practice la alegerea elementului principal
Alegerea elementului principal trebuie s fie n aa fel ca s se micoreze probabilitatea cazului cnd dup divizarea subvectorii (segmentele) s difere mult dup lungime.
Prima strategie: la fiecare divizare alegerea aleatorie (folosind funcia-generator de numere aleatoare) a valorii indicelui elementului principal dintre i, i+1, , j. Neajunsul acestei metode - cheltuieli suplimentare de timp necesare pentru aceast operaie.
A dou strategie: n calitate de elementul principal se alege elementul cu valoarea medie dintr-un set nu mare de elemente. Cel mai simplu i mai uor de examinat setul ce conine trei elemente cu indicii respectiv i, j i (i+j)/2.
Ambele metode micoreaz probabilitatea cazului catastrofal O(n2), doar totui aa situaie nu este exclus. Sortarea rapid ntotdeauna poate s se degenereze. Paradoxal, c sortarea rapid este unul din cei mai buni algoritmi de sortare intern, dar suntem nevoii s ne refuzm de ea n probleme unde limitele superioare de timp (de tip knlog2n) necesare pentru sortarea, sunt critice.
Algoritmul divizrii
Exist mai multe variante ale algoritmului de divizare. Toate din ele urmresc cel puin dou scopuri:
a accelera ciclurile interioare;
a prevedea caracterul aleator a vectorului. Adic de a exclude introducerea ntmpltoare a ordinei n segmentele de divizare din punct de vedere al productivitii generale a algoritmului. Adic trebuie s ne refuzm de orice ncercare de a sorta n procesul de divizare.
Sedgewick R. E. a propus urmtoarea metod de divizare:
a) punem elementul principal n poziia i (l schimbm dac este necesar cu elementul t[i]).
b) divizm subvectorul t[i+1], t[i+2], t[j], cu ajutorul valoarei elementului principal t[i] lsnd pe t[i] la locul su. Se primete divizarea cu poziia intermediar imain, de exemplu:
i j i+1
i j imain
imain+1 imain-1
elemente t[i] elemente t[i]
Structuri de date (n baza C++): Suport de curs S.Pereteatcu, A.Pereteatcu
48
c) schimbm cu locurile elementul t[i] cu elementul t[imain] i dm valoarea imain ca
rezultatul ntors de ctre funcia divide.
template int vector_quicksort::divide(int i, int j)
{
int imain, jmain, imed;
imed =(i+j)/2;
imain = (ncomp++, t[i] < t[imed]) ?
((ncomp++, t[imed] < t[j]) ?
imed
:
(ncomp++, t[i] < t[j]) ? j : i)
:
((ncomp++, t[imed] > t[j]) ?
imed
:
(ncomp++, t[i] > t[j]) ? j : i);
if(imain > i)
swap(i, imain);
imain = i+1, jmain = j;
while(imain < jmain)
{
while((imain < jmain)&&(ncomp++, t[imain] imain)&&(ncomp++, t[jmain] >= t[i]))
jmain--;
if(imain < jmain)
swap(imain, jmain);
}
if(ncomp++, t[imain] > t[i])
imain--;
if(imain > i)
swap(i, imain);
i j imain
imain+1 imain-1
elemente t[imain] elemente t[imain] elementul principal
Structuri de date (n baza C++): Suport de curs S.Pereteatcu, A.Pereteatcu
49
return imain;
}
Este clar c funcia divide() are complexitatea O(n). Ciclul exterior while(imain < jmain)
{
}
verific fiecare element al vectorului t[0], t[i], t[n-1] cel mai mult de dou ori, dar restul operaiilor cere un timp fix.
n funcia main() crem un vector si-il sortatm prin metoda quicksort: void main()
{
clrscr();
vector_quicksort gr("Stud.txt");
gr.show("Unsorted group:\n","");
gr.quicksort();
gr.show("Group sorted by name:\n","");
cout
Structuri de date (n baza C++): Suport de curs S.Pereteatcu, A.Pereteatcu
50
4. Gray, 1968, 900
5. Green, 1987, 350
6. Magenta, 1983, 600
7. Orange, 1984, 550
8. Red, 1980, 450
9. White, 1980, 600
10. Yellow, 1988, 300
End of vector. Press any key ...
n=10, ncomp=39, n*log2(n)=33.2193, n*n=100
Analiza rezultatelor rmne ca exerciiu.
Dac vrem s sortm dup anul de natere, atunci declarm n baza clasei usual_elem clasa year_elem la care suprascriem funcia cmp(). //
// c l a s s "y e a r _ e l e m"
//
class year_elem : public usual_elem
{
public:
year_elem()
{
}
year_elem(char* init_name, int init_year, double init_salary):
usual_elem(init_name, init_year, init_salary)
{
}
virtual int cmp(elem& e2)
{
int result;
if(this->year < ((year_elem&)e2).year)
result=-1;
else
if(this->year > ((year_elem&)e2).year)
result=1;
else
result=0;
return result;
}
};
n funcia main() instaniem clasa generic vector_quicksort cu clasa-argument year_elem.
Structuri de date (n baza C++): Suport de curs S.Pereteatcu, A.Pereteatcu
51
void main()
{
clrscr();
vector_quicksort gr("Stud.txt");
gr.show("Unsorted group:\n","");
gr.quicksort();
gr.show("Group sorted by year:\n","");
cout
Structuri de date (n baza C++): Suport de curs S.Pereteatcu, A.Pereteatcu
52
n sfrit declarm n baza clasei usual_elem clasa derivat salary_elem care compar obiecte dup salariu. //
// c l a s s "s a l a r y _ e l e m"
//
class salary_elem : public usual_elem
{
public:
salary_elem()
{
}
salary_elem(char* init_name, int init_year, double init_salary):
usual_elem(init_name, init_year, init_salary)
{
}
virtual int cmp(elem& e2)
{
int result;
if(this->salary < ((salary_elem&)e2).salary)
result=-1;
else
if(this->salary > ((salary_elem&)e2).salary)
result=1;
else
result=0;
return result;
}
};
n funcia main() instaniem clasa generic vector_quicksort cu clasa-argument salary_elem. void main()
{
clrscr();
vector_quicksort gr("Stud.txt");
gr.show("Unsorted group:\n","");
gr.quicksort();
gr.show("Group sorted by salary:\n","");
cout
Structuri de date (n baza C++): Suport de curs S.Pereteatcu, A.Pereteatcu
53
Structuri de date (n baza C++): Suport de curs S.Pereteatcu, A.Pereteatcu
54
numrul maxim P(n) de elemente nscrise simultan n stiv, care este i adncimea maxim a apelurilor recursive, satisface relaiei
2
1)(n
PnP , adic )0(1...111)(2log
PnPn
Lund n consideraie, c P(0)=0, obinem c P(n)i)
{
int imain=divide(i,j);
if(imain-i > j-imain)
{//ncepem cu intervalul stng
quicksort_intern(i,imain-1);
quicksort_intern(imain+1,j);
}
else
{//ncepem cu intervalul drept
quicksort_intern(imain+1,j);
quicksort_intern(i,imain-1);
}
}
}
Deoarece modificarea introdus nu va schimba afirile obinute prin exemplele de sortare precedente, nu le mai repetm.
Complexitatea spaial se reduce n aa fel la mrimea P(n) ).(log2 nO Apreciem complexitatea
temporal T(n). Fiindc divizarea are complexitatea O(n), avem:
)1()0()()( imainnTimainTnOnT . Deci, totul depinde de imain, adic cum vectorul va
fi divizat de ctre funcia divide().
O situaie ideal care ar putea fi obinut prin aplicarea principiului de echilibru, const n
segmentarea vectorului aproximativ n dou pari egale, aa ca 2n
imain . Atunci
),log()(...)()(...8
24
22
2)(
42
22)(
22)()(
2 nnOnOnOnOn
Tn
On
OnO
nT
nOnO
nTnOnT
Structuri de date (n baza C++): Suport de curs S.Pereteatcu, A.Pereteatcu
55
fiindc T(0)=0. Deci, T(n)=O(nlog2n), precum coeficientul la nlog2n este acelai ca i coeficientul pe lng n la complexitatea mpririi.
Aadar, metoda obine O(nlog2n) ce este limita de jos pentru complexitatea algoritmilor de sortare bazai pe compararea cheilor.
Dac divizarea sistematic se obine lng primul sau lng ultimul elemente ale subvectorilor cercetai (adic permanent imain=i, sau imain=j), atunci fiecare dat rmne de sortat o parte a subvectorului, n care numrul de elemente este cu o unitate mai mic dect subvectorul precedent, i rezult c complexitatea va fi )()1(...)1()()1()1()()( 2nOOnOnOnTOnOnT .
n acest caz sortarea rapid are complexitatea teoretic asemntoare cu complexitatea celor mai ri algoritmi de sortare, de exemplu sortarea prin metoda bulelor. Dar complexitatea practic probabil va fi i mai mare, din cauza timpului necesar pentru realizarea recursiei dirijate de stiv. Pentru sortarea rapid este artat teoretic c complexitatea medie apreciat pentru probabilitile egale a tuturor permutrilor este egal cu O(nlog2n) cu aproximativ 2nlog2n comparaii a cheilor, de asemenea este artat c probabilitatea celui mai nefavorabil caz cu complexitatea O(n2) este destul de mic.
Posibilitatea celui mai nefavorabil caz nu este exclus cnd datele sunt deja sortate sau parial sortate (poate fi i n ordine invers).
Paradoxul sortrii rapide n contrastul cu sortarea prin inserie sau chiar prin metoda bulelor, const n aceea c sortarea rapid i pierde calitatea la vectori parial ordonai. Faptul acesta este incomod, fiindc necesitatea de a sorta datele aproape sortate destul de des se ntlnete n practic.
mbuntirea sortrii rapide
Ca sortarea rapid s devin real un algoritm efectiv, ea mai cere nc o mbuntire. Este evident, c n versiunile precedente recursia i alegerea elementului principal devin destul de grele pentru subvectori mici. Sortarea rapid nu poate fi aplicat la vectori mici. De aceea recursia trebuie oprit cnd dimensiunea subvectorului devine mai mic dect careva constant, numit prag. Dup aceasta se folosete metoda, eficacitatea creia poate s se mbunteasc la datele parial sortate, de exemplu sortarea prin inserie simpl.
D. Knuth a obinut c valoarea optimal teoretic a pragului este egal cu 9.
n practic rezultatele bune ne dau valorile pragului de la 8 pn la 20, iar valoarea optim se conine ntre 14 i 16. //
// c l a s s " v e c t o r o p t i m q u i c k s o r t "
//
template class vector_optim_quicksort:
public vector_quicksort
{
public:
vector_optim_quicksort(char* file_name, int threshold_init=15):
Structuri de date (n baza C++): Suport de curs S.Pereteatcu, A.Pereteatcu
56
vector_quicksort(file_name)
{
threshold=threshold_init;
if(threshold=n || j==-1)
j=n-1;
if(ij)
i=0;
quicksort_intern(i, j);
}
protected:
int threshold;
void quicksort_intern(int i, int j);
void insertsort(int i, int j);
};
template
void vector_optim_quicksort::quicksort_intern(int i, int j)
{
if(j-i+1>threshold)
{
int imain=divide(i,j);
if(imain-i > j-imain)
{
quicksort_intern(i,imain-1);
quicksort_intern(imain+1,j);
}
else
{
quicksort_intern(imain+1,j);
quicksort_intern(i,imain-1);
}
}
else
insertsort(i, j);
}
Structuri de date (n baza C++): Suport de curs S.Pereteatcu, A.Pereteatcu
57
template
void vector_optim_quicksort::insertsort(int i, int j)
{
for(int k = i+1; ki)&&(ncomp++, t[l]
Structuri de date (n baza C++): Suport de curs S.Pereteatcu, A.Pereteatcu
58
2. Red, 1980, 450
3. Blue, 1981, 500
4. Gray, 1968, 900
5. Orange, 1984, 550
6. White, 1980, 600
7. Cyan, 1975, 800
8. Yellow, 1988, 300
9. Magenta, 1983, 600
10. Black, 1981, 500
End of vector. Press any key ...
Group sorted by year:
1. Gray, 1968, 900
2. Cyan, 1975, 800
3. Red, 1980, 450
4. White, 1980, 600
5. Blue, 1981, 500
6. Black, 1981, 500
7. Magenta, 1983, 600
8. Orange, 1984, 550
9. Green, 1987, 350
10. Yellow, 1988, 300
End of vector. Press any key ...
n=10, ncomp=37, n*log2(n)=33.2193, n*n=100
Pentru vectorul concretizat cu clasa salary_elem Unsorted group:
1. Green, 1987, 350
2. Red, 1980, 450
3. Blue, 1981, 500
4. Gray, 1968, 900
5. Orange, 1984, 550
6. White, 1980, 600
7. Cyan, 1975, 800
8. Yellow, 1988, 300
9. Magenta, 1983, 600
10. Black, 1981, 500
End of vector. Press any key ...
Group sorted by salary:
1. Yellow, 1988, 300
2. Green, 1987, 350
3. Red, 1980, 450
4. Blue, 1981, 500
5. Black, 1981, 500
Structuri de date (n baza C++): Suport de curs S.Pereteatcu, A.Pereteatcu
59
6. Orange, 1984, 550
7. White, 1980, 600
8. Magenta, 1983, 600
9. Cyan, 1975, 800
10. Gray, 1968, 900
End of vector. Press any key ...
n=10, ncomp=33, n*log2(n)=33.2193, n*n=100
n urmtorul tabel este prezentat numrul de comparri efectuate la sortarea obiectelor vector_optim_quicksort create pe baza fiierului stud.txt pentru diferite valori ale pragului i clase de concretizare.
Cmpul de sortare Prag
name year salary
0 39 42 43 1 39 42 43 2 37 37 41 3 35 37 38 4 32 37 33 5 29 34 28 6 29 34 28 7 29 34 28 8 29 34 28 9 29 34 28
10 30 28 25 11 30 28 25
Analiza rezultatelor prezentate n acest tabel rmne ca exerciiu.
3.5. Sortarea prin inserie
Inserie simpl
Ideea principal a sortrii prin inserie (engl. Insert sort) este simpl: alegem careva element, sortm celelalte elemente, inserm elementul ales (adic l includem) la locul potrivit printre altele deja sortate. void recursivinsertsort(int i, int j)
{
if(j>i)
{
recursivinsertsort(i, j-1);
for(int l=j; (l>i)&&(ncomp++, t[l]
Structuri de date (n baza C++): Suport de curs S.Pereteatcu, A.Pereteatcu
60
n forma nerecursiv sortarea prin inserie se scrie astfel: void insertsort(int i, int j)
{
int k;
for(k=i+1; ki)&&(ncomp++,t[l]
Structuri de date (n baza C++): Suport de curs S.Pereteatcu, A.Pereteatcu
61
Dac vectorul iniial este total sortat, atunci complexitatea este egal O(n). n cazul general algoritmul folosete orice ordine parial, ce se conine n vector. Dac mai lum n consideraie i simplitatea algoritmului, ajungem la concluzie c acest algoritm este cel mai bun pentru finisarea lucrului a metodelor mai pretenioase, cum de exemplu este sortarea rapid. Adic pentru finisarea lucrului algoritmilor, care destul de repede mpart vectorul n mai multe pri aproape sortate, dar cer destul de mult timp i se nduesc la sortarea final a subvectorilor mici.
Metoda lui Shell
Neajunsul esenial al sortrii prin inserie simpl const n aceia, c la fiecare pas de mutare elementul care se mut, se deplaseaz doar cu o poziie. Fiecare din aceste mutri elimin exact o inversie. n rezultat numrul total de mutri a datelor este egal cu numrul iniial de inversii, care n
probabilitatea medie este: 4
)1(2*2
)1(2
2
nnnncn .
Donald L. Shell n anul 1959 a propus n loc de inseria sistematic a elementului cu indicele i n sub vectorul elementelor precedente (modul care contrazice principiului de echilibru), de a include acest element n sublist, coninnd elemente cu indicii i-h, i-2h, i-3h, , unde h o constant pozitiv (pas).
Astfel se formeaz vectorul, n care hseria elementelor (elemente care se afl la distana h unul de la altul) se sorteaz deoparte.
Dup ce au fost sortate deoparte neintersectatele hserii, procesul ncepe cu valori noi h'
Structuri de date (n baza C++): Suport de curs S.Pereteatcu, A.Pereteatcu
62
Crem n baza clasei generice vector clasa generic vector_Shellsort dotat cu algoritmul de sortare prin metoda lui Shell: //
// c l a s s "v e c t o r _ S h e l l s o r t "
//
template class vector_Shellsort: public vector
{
public:
vector_Shellsort(char* file_name): vector(file_name)
{
}
void Shellsort();
};
template
void vector_Shellsort::Shellsort()
{
int h;
int i, j, k;
el tmp;
//definirea pasului iniial
h=1;
while(h
Structuri de date (n baza C++): Suport de curs S.Pereteatcu, A.Pereteatcu
63
}
}
//micorarea incrementului
h=h/3;
} while(h>0);
}
Observaii: 1. n locul recalculrii pailor secveniali h se poate de obinut pe ei din calcularea preventiv i
stocarea ntr-un vector adugtor:
2. Se poate de unit buclele dup k i dup i, nlocuind schimburi cu semischimburi;
3. Sortarea prin metoda lui Shell este instabil, i problema aceasta nu poate fi rezolvat uor.
n funcia main() instaniem clasa vector_Shellsort concretizat cu clasa usual_elem, afim vectorul iniial, l sortm prin metoda lui Shell, afim vectorul sortat i informaii legate de aprecierea complexitii: void main()
{
clrscr();
vector_Shellsort gr("Stud.txt");
gr.show("Unsorted group:\n","");
gr.Shellsort();
gr.show("Group sorted by name:\n","");
cout
Structuri de date (n baza C++): Suport de curs S.Pereteatcu, A.Pereteatcu
64
8. Yellow, 1988, 300
9. Magenta, 1983, 600
10. Black, 1981, 500
End of vector. Press any key ...
Group sorted by name:
1. Black, 1981, 500
2. Blue, 1981, 500
3. Cyan, 1975, 800
4. Gray, 1968, 900
5. Green, 1987, 350
6. Magenta, 1983, 600
7. Orange, 1984, 550
8. Red, 1980, 450
9. White, 1980, 600
10. Yellow, 1988, 300
End of vector. Press any key ...
n=10, ncomp=30, n*log2(n)=33.2193, n*n=100
Dup cum se vede numrul de comparri a coincis cu numrul de comparri la inserie simpl.
nlocuim n funcia main() clasa usual_elem cu clasa year_elem, atunci vom obine: Unsorted group:
1. Green, 1987, 350
2. Red, 1980, 450
3. Blue, 1981, 500
4. Gray, 1968, 900
5. Orange, 1984, 550
6. White, 1980, 600
7. Cyan, 1975, 800
8. Yellow, 1988, 300
9. Magenta, 1983, 600
10. Black, 1981, 500
End of vector. Press any key ...
Group sorted by year:
1. Gray, 1968, 900
2. Cyan, 1975, 800
3. Red, 1980, 450
4. White, 1980, 600
5. Blue, 1981, 500
6. Black, 1981, 500
7. Magenta, 1983, 600
8. Orange, 1984, 550
9. Green, 1987, 350
10. Yellow, 1988, 300
Structuri de date (n baza C++): Suport de curs S.Pereteatcu, A.Pereteatcu
65
End of vector. Press any key ...
n=10, ncomp=28, n*log2(n)=33.2193, n*n=100
Analiza rezultatelor rmne ca exerciiu.
Dac vom nlocui n funcia main() clasa year_elem cu clasa salary_elem, vom obine: Unsorted group:
1. Green, 1987, 350
2. Red, 1980, 450
3. Blue, 1981, 500
4. Gray, 1968, 900
5. Orange, 1984, 550
6. White, 1980, 600
7. Cyan, 1975, 800
8. Yellow, 1988, 300
9. Magenta, 1983, 600
10. Black, 1981, 500
End of vector. Press any key ...
Group sorted by salary:
1. Yellow, 1988, 300
2. Green, 1987, 350
3. Red, 1980, 450
4. Blue, 1981, 500
5. Black, 1981, 500
6. Orange, 1984, 550
7. White, 1980, 600
8. Magenta, 1983, 600
9. Cyan, 1975, 800
10. Gray, 1968, 900
End of vector. Press any key ...
n=10, ncomp=25, n*log2(n)=33.2193, n*n=100
Analiza rezultatelor rmne ca exerciiu.
Metoda lui Shell esenial ntrece inseria simpl pentru n mai mari de 100. Numrul necesar de comparri n mediu are ordinul 1.66n1.25 pentru un n destul de mare. Analiznd tabelul urmtor:
n 1.66n1.25 nlog2n
10 29,5 33.2193
100 525 664
1000 9335 9966
10000 166000 132877
105 2,95*106 1,66*106
106 5,25*107 1,99*107
Structuri de date (n baza C++): Suport de curs S.Pereteatcu, A.Pereteatcu
66
vedem c metoda lui Shell rezist competiia cu metodele O(nlog2n) pn la n=105.
Sortarea Shell ru se adapteaz la sistemele cu memorie virtual (adic care acoper vectorul cu intervale largi).
3.6. Sortarea prin selecie
Selecie simpl
Ideea acestei metode de sortare (engl. Selection sort) este foarte simpl: se selecteaz elementul maxim din tablou i i se schimb locul cu ultimul element; n continuare se caut elementul maxim pn la ultimul i i se schimb cu penultimul elementul. La fiecare parcurgere se examineaz toate elementele ale vectorului care au rmas neordonate, elementul maxim din care va fi alturat la cele ordonate.
n form nerecursiv selecie simpl const din n-1 etape. La etapa k se caut elementul cu cheia maxim dintre elementele care nu sunt ordonate pn la capt i-l leag la poziia n-k.
Exemplu: void selectsort()
{
int imax, i, j;
for(i=n-1; i>0; i--)
{
imax=i;
for(j=0; jt[imax])
imax=j;
swap(i,imax);
// aici sub vectorul ]1[][ ntit este sortat(invarianta buclei)
}
}
Acest algoritm are complexitatea O(n2) n toate cazurile. Numrul de ndepliniri a ciclului interior
este egal 2
)1( nn.
3.7. Sortarea arborescent (piramidal, heapsort)
Sortarea arborescent provine de la selecia simpl. Neajunsul principal al sortrii prin selecie simpl const n aceea c comparaiile fcute la fiecare etap dau mult mai multe informaii dect cele care se folosesc efectiv pentru a pune elementul curent la locul potrivit. Pentru a obine o mbuntire esenial, trebuie de folosit o structur de date mai dezvoltat, permindu-i pe ct se poate, s pstreze informaia, obinut secvenial la verificare. De exemplu, dac t[i]>=t[k], iar t[k]>=t[j], atunci t[i]>=t[j].
Structuri de date (n baza C++): Suport de curs S.Pereteatcu, A.Pereteatcu
67
Sortarea arborescent folosete un arbore binar concret, din care este uor de extras elemente cu chei maxime. Acest arbore se numete arbore de maximizare, el posed proprietatea c elementul n fiecare vrf are cheia mai mare sau egal dect cheile ale fiilor dac aceti fii exist. La aplicarea arborilor de maximizare apare problema de reorganizare cnd doi subarbori ai rdcinii sunt de maximizare, iar arborele ntreg nu este de maximizare.
n acest caz pentru reorganizarea arborelui, adic pentru l preface n arbore de maximizare, trebuie s facem civa pai. ncepnd de la rdcin ne deplasm n direcia maximal interschimbnd elementele.
Arborele binar plin, adic, la care pn la orice nivel exist toate nodurile cu posibila excepie pentru cele mai drepte noduri ale ultimului nivel. Astfel de arbore poate fi reprezentat sub form de vector.
Nodului cu indice i i corespunde nodurile cu indicii 2*i+1 (fiul stng, dac 2*i+1
Structuri de date (n baza C++): Suport de curs S.Pereteatcu, A.Pereteatcu
68
{
}
void heapsort();
protected:
void reorganization(int i, int j);
void planting();
void maxtreesort();
};
Descriem funcia de reorganizare pentru subarbori.
Fie: i, j o pereche de indici astfel c 0
Structuri de date (n baza C++): Suport de curs S.Pereteatcu, A.Pereteatcu
69
aa fel complexitatea reorganizrii este O(log2(j-i+1)), mai concret ea se ndeplinete cu 2(log2(j-i+1)) comparaii i log2(j-i+2) interschimbri.
Algoritmul de sortare arborescent const din dou etape fiecare din care folosete reorganizarea:
Plantare (planting) transform vectorul iniial n vectorul cu arbore de maximizare;
Sortarea arborelui de maximizare (maxtreesort) face sortarea lund n consideraie arborii de maximizare.
template void vector_heapsort::heapsort()
{
planting();
maxtreesort();
}
La plantare reorganizarea se aplic la aa indicii i subarborii la care, dac exist, sunt arbori de maximizare. ncepem de la elementul t[(n-1)/2], fiindc elementul cu indice mai mare nu are subarbori. template void vector_heapsort::planting()
{
for(int i=(n-1)/2; i>=0; i--)
reorganization(i, n-1);
}
Complexitatea plantrii poate fi dedus din complexitatea reorganizrii, adic din subvectorii cercetai, corespunztori vrfurilor arborelui:
1. adncimea sub vectorului h=[log2n]+1 vectorul t[0]t[n-1];
2. adncimea sub vectorului h-1 vectorii t[1]t[n-1], t[2]t[n-1];
3. adncimea sub vectorului h-2 vectorii t[3]t[n-1], t[4]t[n-1], t[5]t[n-1],
t[6]t[n-1];
4.
n aa fel complexitatea poate fi scris n forma: O(1*h*2*(h-1)+...+2h-2*2)=O(2h-1)=O(n).
Dup plantare t[0] a devenit elementul maximal, el trebuie sa fie interschimbat cu elementul t[n-1], dup ce rmne de sortat sub vectorul t[0]t[n-2], dar acest sub vector va fi arbore de maximizare cu unic excepie posibil, privind elementul t[0] (precedentul t[n-1]), de aceea la acest subvector aplicm reorganizarea, pentru a obine maximul subvectorului n t[0], pe care interschimbm cu t[n-2], etc. template void vector_heapsort::maxtreesort()
{
for (int i=(n-1);i>=1;i--)
{
swap (0, i);
reorganization(0, i-1);
}
Structuri de date (n baza C++): Suport de curs S.Pereteatcu, A.Pereteatcu
70
}
Complexitatea acestei proceduri este )()(1
1,0
n
iihOnT , unde h0,i - adncimea corespunztoarea
subarborelui t[0]t[i], adic 1log 2,0 ih i . Deci, obinem c T(n)=O(nlog2n). n aa fel complexitatea algoritmului de sortare arborescenta este O(n+nlog2n)=O(nlog2n).
Aceasta este complexitatea att maximal ct i cea medie fiindc nimic n-am presupus despre repartizarea iniial a elementelor. Sortarea arborescent este cel mai sigur algoritm de sortare .
void main()
{
clrscr();
vector_heapsort gr("Stud.txt");
gr.show("Unsorted group:\n","");
gr.heapsort();
gr.show("Group sorted by name:\n","");
cout
Structuri de date (n baza C++): Suport de curs S.Pereteatcu, A.Pereteatcu
71
6. Magenta, 1983, 600
7. Orange, 1984, 550
8. Red, 1980, 450
9. White, 1980, 600
10. Yellow, 1988, 300
End of vector. Press any key ...
n=10, ncomp=41, n*log2(n)=33.2193, n*n=100
nlocuim n funcia main() clasa usual_elem cu clasa year_elem, atunci vom obine: Group sorted by year:
1. Gray, 1968, 900
2. Cyan, 1975, 800
3. White, 1980, 600
4. Red, 1980, 450
5. Blue, 1981, 500
6. Black, 1981, 500
7. Magenta, 1983, 600
8. Orange, 1984, 550
9. Green, 1987, 350
10. Yellow, 1988, 300
End of vector. Press any key ...
n=10, ncomp=38, n*log2(n)=33.2193, n*n=100
nlocuim n funcia main() clasa year_elem cu clasa salary_elem, atunci vom obine: Group sorted by salary:
1. Yellow, 1988, 300
2. Green, 1987, 350
3. Red, 1980, 450
4. Black, 1981, 500
5. Blue, 1981, 500
6. Orange, 1984, 550
7. White, 1980, 600
8. Magenta, 1983, 600
9. Cyan, 1975, 800
10. Gray, 1968, 900
End of vector. Press any key ...
n=10, ncomp=40, n*log2(n)=33.2193, n*n=100
Analiza rezultatelor rmne ca exerciiu.
Structuri de date (n baza C++): Suport de curs S.Pereteatcu, A.Pereteatcu
72
3.8. Comparaii practice ai diferiilor algoritmi de sortare
S-au folosit diferite principii de sortare i poate prea greu de ales algoritmul potrivit. El depinde de muli factori. Dar fiecare din aceti algoritmi se poate uor i repede de reprogramat. De aceea adresarea la Bubblesort din cauza c este uor de scris, nu poate fi justificat nicicum.
La alegerea algoritmului de sortare pot fi date urmtoarele recomandri: - pentru n mici (100) i poate mai mari, dac nu ncercm s ctigm cteva microsecunde,
sortarea prin inserie simpl ne d un rezultat destul de bun, n special dac datele sunt deja
parial sortate;
- pentru n de la cteva sute pn la cteva mii, metoda Shell ne d un rezultat excelent. n
sistemele cu memorie virtual ea nu trebuie folosit, dac vectorul se aranjeaz pe un numr
mare de pagini;
- pentru n >100 (de exemplu) quicksort este probabil, cel mai bun algoritm n caz general; dar
el poate s creasc pn la O(n2) cu probabilitatea ne nul (probabilitatea totui este destul
de mic, dac este bine scris divizarea);
- pentru n>100 sortarea Heapsort cere aproape de dou ori mai mult timp n mediu, fa de
sortare rapid, dar este garantat comportarea ei cu O(nlogn).
n comparaiile experimentale ale diferitor metode de sortare, a fost folosit un vector real, n care fiecare element era cheia lui proprie. Vectorul a fost alctuit din elemente aleatorie, ceia ce puin a favorizat sortarea rapid.
Observaie: Concluziile pot fi diferite n dependen de preul de comparare a cheilor ce se compar, de modul de interschimbare a elementelor, i de alte operaii:
N
metoda
10 100 1000 10000 25000 50000
Bublesort 0,16 20 2400
Extractsort 0,12 7,3 680
Insertsort 0,12 6,7 610
Shellsort 0,07 2 37 600 1800 4200
Heapsort 0,2 3,5 50 660 1830 3960
Quicksort 0,07 2 28 365 1000 2140
Structuri de date (n baza C++): Suport de curs S.Pereteatcu, A.Pereteatcu
73
4. STRUCTURI DINAMICE DE DATE
4.1. Noiune de structura dinamic de date
Definiie:
Structura dinamic de date (SDD) este o aa structur de date numrul de elemente la care se schimb n procesul de utilizare a ei.
Se adaug elemente noi, se elimin careva elemente din cele existente, precum adugrile i eliminrile se efectueaz n mod independent unele de altele.
Pentru structuri dinamice de date este de caracter amplasarea elementelor mprtiat prin memorie n dependen de alocarea locurilor pentru ele n timpul de adugare a lor.
Tipuri de structuri dinamice de date se difer ntre ele prin organizarea legturilor ntre elementele care ntr n componena SDD, prin ordine de adugare (nscriere) a elementelor noi, prin ordine de accesare a elementelor, prin ordine de nlturare (tergere) a elementelor existente,