4 Mergesort in clasele tablou<T>
si lista<E>
7.4.1 O solutie neinspirata
Desi eficient in privinta timpului, algoritmul de sortare prin interclasare
are un handicap important in ceea ce priveste memoria necesara. Intr-adevar,
orice tablou de n elemente este sortat intr-un timp in Q(n log n),
dar utilizand un spatiu suplimentar de memorie[*]
de 2n elemente. Pentru a reduce consumul de memorie, in implementarea
acestui algoritm nu vom utiliza variabilele intermediare U
si V de tip tablou<T>,
ci o unica zona de auxiliara de n elemente.
Convenim sa implementam procedura mergesort din Sectiunea 7.3 ca membru
private al clasei parametrice tablou<T>.
Invocarea acestei proceduri se va realiza prin functia membra
template <class T>
<T>& tablou<T>::sort( ) {
T *aux = new T[ d ]; // alocarea zonei de interclasare
mergesort( 0, d, aux ); // si sortarea propriu-zisa
delete [ ] aux; // eliberarea zonei alocate
return *this;
}
Am preferat aceasta maniera de incapsulare din urmatoarele
doua motive:
Alocarea si eliberarea spatiului
suplimentar necesar interclasarii se face o singura data, inainte si dupa terminarea
sortarii. Functia mergesort(), ca functie recursiva,
nu poate avea controlul asupra alocarii si eliberarii acestei zone.
Algoritmul mergesort
are trei parametri care pot fi ignorati la apelarea functiei de sortare. Acestia
sunt: adresa zonei suplimentare de memorie si cei doi indici prin care se incadreaza
elementele de sortat din tablou.
Dupa cum se poate vedea in Exercitiul 7.7, implementarea interclasarii se simplifica
mult prin utilizarea unor valori santinela in tablourile de interclasat. Functia
mergesort():
template <class T>
<T>::mergesort( int st, int dr, T *x ) {
if ( dr - st > 1 ) {
// mijlocul intervalului
int m = ( st + dr ) / 2;
// sortarea celor doua parti
mergesort( st, m );
mergesort( m, dr );
// pregatirea zonei x pentru interclasare
int k = st;
for ( int i = st; i < m; ) x[ i++ ] = a[ k++ ];
for ( int j = dr; j > m; ) x[ --j ] = a[ k++ ];
// interclasarea celor doua parti din x in zona a
i = st; j = dr - 1;
for ( k = st; k < dr; k++ )
a[ k ] = x[ j ] > x[ i ]? x[ i++ ]: x[ j-- ];
}
}
se adapteaza surprinzator de simplu la utilizarea
santinelelor. Nu avem decat sa transferam in zona auxiliara cele doua
jumatati deja sortate, astfel incat valorile maxime sa fie la mijlocul acestei
zone. Altfel spus, prima jumatate va fi transferata crescator, iar cea de-a
doua descrescator, in continuarea primei jumatati. Incepand interclasarea cu
valorile minime, valoarea maxima din fiecare jumatate este santinela pentru
cealalta jumatate.
Sortarea prin interclasare prezinta un avantaj foarte
important fata de alte metode de sortare deoarece elementele de sortat sunt
parcurse secvential, element dupa element. Din acest motiv, metoda este
potrivita pentru sortarea fisierelor sau listelor. De exemplu, procedura de
sortare prin interclasare a obiectelor de tip lista<E>
template <class E>
<E>& lista<E>::sort() {
if ( head )
head = mergesort( head );
return *this;
}
rearanjeaza nodurile in ordinea crescatoare a cheilor, fara a
folosi noduri sau liste temporare. Pretul in spatiu suplimentar de memorie este
totusi platit, deoarece orice lista inlantuita necesita memorie in ordinul
numarului de elemente pentru realizarea inlantuirii.
Conform algoritmului mergesort, lista se imparte in doua parti egale,
iar dupa sortarea fiecareia se realizeaza interclasarea. Impartirea listei in
cele doua parti egale nu se poate realiza direct, ca in cazul tablourilor, ci
in mai multi pasi. Astfel, vom parcurge lista pana la sfarsit, pentru a putea
determina elementul din mijloc. Apoi stabilim care este elementul din mijloc
si, in final, izolam cele doua parti, fiecare in cate o lista. In functia mergesort():
template <class E>
<E>* mergesort ( nod<E> *c ) {
if ( c && c->next ) {
// sunt cel putin doua noduri in lista
nod<E> *a = c, *b;
for ( b = c->next; b; a = a->next )
if ( b->next ) b = b->next->next;
else break;
b = a->next; a->next = 0;
return merge( mergesort( c ), mergesort( b ) );
}
else
// lista contine cel mult un nod
return c;
}
impartirea listei se realizeaza printr-o singura
parcurgere, dar cu doua adrese de noduri, a si b. Principiul folosit este urmatorul: daca b inainteaza in parcurgerea listei
de doua ori mai repede decat a,
atunci cand b a ajuns la
ultimul nod, a este la
nodul de mijloc al listei.
Spre deosebire de algoritmul mergesort, sortarea listelor prin interclasare nu deplaseaza
valorile de sortat. Functia merge()
interclaseaza listele de la adresele a si b prin simpla modificare a legaturilor nodurilor.
template <class E>
nod<E>* merge( nod<E> *a, nod<E> *b ) {
nod<E> *head; // primul nod al listei interclasate
if ( a && b )
// ambele liste sunt nevide;
// stabilim primul nod din lista interclasata
if ( a->val > b->val ) { head = b; b = b->next; }
else { head = a; a = a->next; }
else
// cel putin una din liste este vida;
// nu avem ce interclasa
return a? a: b;
// interclasarea propriu-zisa
nod<E> *c = head; // ultimul nod din lista interclasata
while ( a && b )
if ( a->val > b->val ) { c->next = b; c = b; b = b->next;
else { c->next = a; c = a; a = a->next; }
// cel putin una din liste s-a epuizat
c->next = a? a: b;
// se returneaza primul nod al listei interclasate
return head;
}
Functia de sortare mergesort(), impreuna cu cea de interclasare merge(), lucreaza exclusiv asupra
nodurilor. Deoarece aceste functii sunt invocate doar la nivel de lista, ele nu
sunt membre in clasa nod<E>,
ci doar friend fata de
aceasta clasa. Incapsularea lor este realizata prin mecanismul standard al
limbajului C++.
Desi aceste functii apartin domeniului global, ele nu pot fi invocate de aici
datorita obiectelor de tip nod<E>,
obiecte accesibile doar din domeniul clasei lista<E>. Aceasta maniera de incapsulare nu
este complet sigura, deoarece, chiar daca nu putem manipula obiecte de tip nod<E>, totusi putem lucra cu
adrese de nod<E>.
De exemplu, functia
void f( ) {
mergesort( (nod<int> *)0 );
}
trece de compilare, dar efectele ei la rularea programului
sunt imprevizibile.
Prezenta functiilor de sortare in tablou<T> si lista<E> (de fapt si in nod<E>) impune completarea
claselor T si E cu operatorul de comparare >. Orice tentativa de a defini
(atentie, de a defini si nu de a sorta) obiecte de tip tablou<T> sau lista<E> este semnalata ca
eroare de compilare, daca tipurile T sau E nu au definit acest operator. Situatia apare,
deoarece generarea unei clase parametrice implica generarea tuturor functiilor
membre. Deci, chiar daca nu invocam functia de sortare pentru tipul tablou<T>, ea este totusi
generata, iar generarea ei necesita operatorul de comparare al tipului T.
De exemplu, pentru a putea lucra cu liste de muchii, lista<muchie>, sau tablouri
de tablouri, tablou< tablou<T>
>, vom implementa operatorii de comparare pentru clasa muchie si clasa tablou<T>. Muchiile sunt
comparate in functie de costul lor, dar cum vom proceda cu tablourile? O
solutie este de a lucra conform ordinii lexicografice, adica de a aplica
aceeasi metoda care se aplica la ordonarea numelor in cartea de telefoane, sau
in catalogul scolar:
template <class T>
operator > ( const tablou<T>& a, const tablou<T>& b )
// minumul elementelor
int as = a.size( ), bs = b.size( );
int n = as < bs? as: bs;
// comparam pana la prima diferenta
for ( int i = 0; i < n; i++ )
if ( a[ i ] != b[ i ] ) return a[ i ] > b[ i ];
// primele n elemente sunt identice
return as > bs;
}
Atunci cand operatorii de comparare nu prezinta interes, sau
nu pot fi definiti, ii putem implementa ca functii inefective. Astfel, daca
avem nevoie de un tablou de liste sau de o lista de liste asupra carora nu vom
aplica operatii de sortare, va trebui sa definim operatorii inefectivi:
template <class E>
>( const lista<E>&, const lista<E>& ) {
return 1;
}
In concluzie, extinderea claselor tablou<T> si lista<E> cu functiile de sortare nu mentine
compatibilitatea acestor clase fata de aplicatiile dezvoltate pana acum.
Oricand este posibil ca recompilarea unei aplicatii in care se utilizeaza, de
exemplu, tablouri sau liste cu elemente de tip XA, XB
etc, sa devina un cosmar, deoarece, chiar daca nu are nici un sens, trebuie sa
completam fiecare clasa XA,
XB etc, cu operatorul de comparare >.
Programarea orientata pe obiect se foloseste tocmai pentru a
evita astfel de situatii, nu pentru a le genera.
7.4.2 Tablouri sortabile si liste sortabile
Sortarea este o operatie care completeaza facilitatile clasei tablou<T>,
fara a exclude utilizarea acestei clase pentru tablouri nesortabile. Din acest
motiv, functiile de sortare nu pot fi functii membre in clasa tablou<T>.
O solutie posibila de incapsulare a sortarii este de a
construi, prin derivare publica din tablou<T>, subtipul tablouSortabil<T>, care sa contina tot ceea ce
este necesar pentru sortare. Mecanismului standard de conversie, de la tipul
derivat public la tipul de baza, permite ca un tablouSortabil<T> sa poata fi folosit oricand
in locul unui tablou<T>.
In continuare, vom prezenta o alta varianta de incapsulare,
mai putin clasica, prin care atributul sortabil este considerat doar in
momentul invocarii functiei de sortatre, nu apriori, prin definirea obiectului
ca sortabil.
Sortarea se invoca prin functia
template <class T>
<T>& mergesort( tablou<T>& t ) {
( tmsort<T> )t;
return t;
}
care consta in conversia tabloului t la tipul tmsort<T>. Clasa tmsort<T> incapsuleaza absolut toate detaliile
sortarii. Fiind vorba de sortarea prin interclasare, detaliile de implementare
sunt cele stabilite in Sectiunea 7.4.1.
template <class T>
class tmsort {
tmsort( tablou<T>& );
T *a; // adresa zonei de sortat
T *x; // zona auxiliara de interclasare
void mergesort( int, int );
};
Sortarea, de fapt transformarea tabloului t intr-un tablou sortat, este
realizata prin constructorul
template <class T>
<T>::tmsort( tablou<T>& t ): a( t.a ) {
x = new T[ t.size( ) ]; // alocarea zonei de interclasare
mergesort( 0, t.size( ) ); // sortarea
delete [ ] x; // eliberarea zonei alocate
}
Dupa cum se observa, in acest constructor se foloseste
membrul privat T *a
(adresa zonei alocate elementelor tabloului) din clasa tablou<T>. Iata de ce, in
clasa tablou<T>
trebuie facuta o modificare (singura dealtfel): clasa tmsort<T> trebuie declarata friend.
Functia mergesort()
este practic neschimbata:
template <class T>
<T>::mergesort( int st, int dr ) {
// …
// corpul functiei void mergesort( int, int, T* )
// din Sectiunea 7.4.1.
// …
}
Pentru sortarea listelor se procedeaza analog, transformand
implementarea din Sectiunea 7.4.1 in cea de mai jos.
template <class E>
<E>& mergesort( lista<E>& l ) {
( lmsort<E> )l;
return l;
}
template <class E>
class lmsort {
lmsort( lista<E>& );
nod<E>* mergesort( nod<E>* );
nod<E>* merge( nod<E>*, nod<E>* );
};
template <class E>
<E>::lmsort( lista<E>& l ) {
if ( l.head )
l.head = mergesort( l.head );
}
template <class E>
<E>* lmsort<E>::mergesort ( nod<E> *c ) {
// …
// corpul functiei nod<E>* mergesort( nod<E>* )
// din Sectiunea 7.4.1.
// …
}
template <class E>
<E>* lmsort<E>::merge( nod<E> *a, nod<E> *b ) {
// …
// corpul functiei nod<E>* merge( nod<E>*, nod<E>* )
// din Sectiunea 7.4.1.
// …
}
Nu uitati de declaratia friend! Clasa lmsort<E> foloseste membrii privati atat din
clasa lista<E>,
cat si din clasa nod<E>,
deci trebuie declarata friend in
ambele.
