Metode de Sortare

Metode de sortare

In cazul unui vector sortat elementul cu indice i este succesorul celor cu indici de la 0 la i-1 si predecesorul celor cu indici de la i+1 la n-1.

Sortarea prin selectie

Sa consideram un vector in care elementele cu indici de la 0 la i-1 sunt deja sortate. Pentru a continua procesul de sortare, dintre elementele ramase (cu indici de la i pana la n-1) trebuie gasit predecesorul tuturor celorlalte (cu indice ipg) si adus in pozitia i.

i-1iipgn-1

. . .. .. .. .. .

elemente sortateelemente nesortate

Sortarea prin selectie a unui vector de intregi:

iVectorul prelucratipg

0105612371294

1356121071291

2356121071292

3356121071295

4356710121297

5356791212107

6356791012126

In acest exemplu elementul selectat dintr-o secventa este marcat prin hasurare, iar locul in care trebuie plasat acesta este marcat prin chenar dublu.

Algoritmul SelSort (X, N)

pentru i de la 0 la n-2

{ determina ipg = indice predecesor global (ipg ( [i, n-1] )

daca ipg > i atunci inverseaza x[i] cu x[ipg], folosind zona tampon aux;

}

Sortarea prin insertie

In cazul sortarii prin insertie se considera ca vectorul este sortat pana la o anumita pozitie si se incearca inserarea urmatorului element pe pozitia potrivita. Daca vectorul ar avea un singur element, el ar fi deja sortat; in cazul unui vector cu 2 elemente, care nu respecta relatia de ordine, este suficienta inversarea acestora. Sa presupunem ca vectorul are mai mult de 2 elemente si ca am sortat deja, in ordine crescatoare, primele i-1 elemente. Pentru a extinde sortarea la i elemente este necesara deplasarea la dreapta, cu o pozitie, a tuturor succesorilor elementului i, urmata de inserarea sa in pozitia corespunzatoare. Aceasta presupune compararea elementului i cu cele deja sortate, situate la stanga sa. Daca aceasta operatie se efectueaza de la dreapta spre stanga, atunci ea poate fi combinata cu cea de deplasare.

jj+1i-1i

. . .. . .. . .. . .

predecesori auxsuccesori aux ( se deplaseaza la dreaptaaux

Sortarea prin insertie a unui vector de intregi:

iVectorul prelucrat

110561237129

251061237129

356101237129

456101237129

535610127129

635671012129

735671012129

835679101212

In acest exemplu elementul care trebuie inserat intr-o secventa deja sortata este marcat cu un chenar dublu, iar succesorii sai, care trebuie deplasati spre dreapta, sunt marcati prin hasurare.

Algoritmul InserSort (x, n)

pentru i de la 1 la n-1

{ copiaza x[i] in aux;

deplaseaza la dreapta succesorii lui aux inlocuieste ultimul element deplasat cu cel din aux }

Sortarea prin metoda bulelor imbunatatita

Aceasta metoda se bazeaza pe faptul ca intr-un vector sortat toate perechile de elemente consecutive trebuie sa respecte relatia de ordine. Daca aceasta relatie nu este respectata, atunci elementele trebuie interschimbate. Verificarea perechilor trebuie reluata pana cand nu mai este necesara nici o interschimbare, dar fiecare noua etapa de verificare se poate opri la perechea din fata celei care a necesitat ultima interschimbare (u_inv), deoarece, evident, perechile urmatoare respecta relatia de ordine.

Sortarea prin metoda bulelor imbunatatita a unui vector de intregi:

limipVectorul prelucratu_inv

6010561237120

151061237121

256101237121

356101237123

456103127124

556103712124

4056103712120

156103712120

256103712122

356310712123

3056371012120

156371012121

253671012121

1053671012120

03567101212

Fiecare pereche analizata este evidentiata printr-un chenar dublu, hasurat in cazul in care elementele trebuie interschimbate. Limita fiecarei etape de verificare este marcata prin linie dubla mai groasa.

Algoritmul B_Sort (x, n)

lim = n - 1;

cat timp lim > 0

{ u_inv = 0

pentru fiecare pereche ip, cu ip de la 0 la lim-1

daca ordine incorecta atunci { interschimba elementele din perechea ip;

u_inv = ip;

}

lim = u_inv;

}

MergeSort - sortare prin divizare si interclasare (fuziune)

In cazul acestei metode vectorul de sortat este divizat in subvectori, prin injumatatiri succesive, cat timp lungimea acestora este > 2. Evident, un subvector de lungime 1 este sortat, iar un subvector de lungime2 necesita cel mult interschimbarea celor doua valori. Subvectorii sortati sunt interclasati succesiv, in ordinea inversa divizarii, obtinand in final vectorul sortat. Deoarece interclasarea necesita un vector auxiliar, sortarea propriu-zisa va fi precedata de alocarea unei zone tampon de aceeasi lungime cu vectorul de sortat.

Pentru a evita copierea rezultatului unei interclasari din vectorul auxiliar in cel de sortat si a reduce astfel numarul de operatii, vectorul initial si cel auxiliar pot fi utilizati alternativ ca sursa si, respectiv, rezultat al operatiei de interclasare. De asemenea, daca analizam exemplele urmatoare:

subvectori sursarezultat interclasare

| 15, 18 | 3, 8, 11 |=>| 3, 8, 11, 15, 18 |

| 2, 5 | 5, 14 |=>| 2, 5, 5, 14 |

observam ca un subvector poate fi predecesorul celuilalt (ultimul element dintr-un subvector este predecesorul primului element din celalalt). In astfel de cazuri interclasarea poate fi inlocuita prin copierea celor doi subvectori, in ordine inversa (primul exemplu) sau pastrand ordinea existenta (al doilea exemplu).

Sortarea prin divizare si fuziune a unui vector de intregi:

Vectorul prelucratsursa, rezlung. subvectoriFaza

10561237129w , v8divizare

105612v , w4divizare

105w , v2tratare pereche

510

612w , v2tratare pereche

561012v , w4fuziune

37129v , w4divizare

37w , v2tratare pereche

129w , v2tratare pereche

912

37912v , w4fuziune

35679101212w , v8fuziune

In acest exemplu frontierele subvectorilor sunt marcate cu linie dubla, iar subvectorii care implica interschimbare sau interclasare sunt evidentiati prin hasurare.

Algoritmul MergeSort ( v, n)

creeaza w - copia vectorului v MSort (n, w, v) - sorteaza cele n elemente din w, obtinand rezultatul in v

elibereaza spatiul ocupat de wAlgoritmul MSort ( n, sursa, rez)

daca n este

> 2:

{ determina dimensiunea primului subvector (j = n / 2)

apeleaza MSort pentru sortarea primelor j elemente din rez in sursa;

apeleaza MSort pentru sortarea ultimelor n-j elemente din rez in sursa;

daca primul subvector sursa il precede pe al doilea atunci copiaza cele n elemente din sursa in rez

altfel daca al doilea subvector sursa il precede pe primul atunci copiaza in rez al doilea subvector, urmat de primul

altfel interclaseaza cei doi subvectori sursa in rez

}

= 2: daca ordine incorecta atunci copiaza in rez in ordine inversa (al doilea, primul)

Algoritmul MSort este un algoritm recursiv.

Algoritmul iterativ MSortI, prezentat in cele ce urmeaza, foloseste interclasarea pentru a construi subvectori sortati de lungimi din ce in ce mai mari.

Algoritmul MSortI ( v, n)

aloca spatiu pentru w;

sorteaza perechile de elemente din v in w; k = 2; sursa = w si rez = v;

cat timp k < n interclaseaza in rez perechi de subvectori sursa de lungime k (ultimul subvector

poate avea lungime < k);

inverseaza sursa si rez;

dubleaza k;

daca rez este w atunci copiaza w in v

elibereaza spatiul ocupat de wSortarea cu MSortI a unui vector de intregi:

Vectorul prelucratsursa, rezLungimi subvectori

105612371512943v , w

510612371215493w , v2 x 5 , 1

561012371215349v , w4 x 2 , 3

356710121215349w , v8 x 1 , 3

334567910121215v , w11

PAGE 1