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-1 i ipg n-1

. . . . . . . . . . .

elemente sortate elemente nesortate

Sortarea prin selectie a unui vector de intregi:

i Vectorul prelucrat ipg

0 10 5 6 12 3 7 12 9 4

1 3 5 6 12 10 7 12 9 1

2 3 5 6 12 10 7 12 9 2

3 3 5 6 12 10 7 12 9 5

4 3 5 6 7 10 12 12 9 7

5 3 5 6 7 9 12 12 10 7

6 3 5 6 7 9 10 12 12 6

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.

j j+1 i-1 i

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

predecesori aux succesori aux  se deplaseaza la dreapta aux

Sortarea prin insertie a unui vector de intregi:

i Vectorul prelucrat

1 10 5 6 12 3 7 12 9

2 5 10 6 12 3 7 12 9

3 5 6 10 12 3 7 12 9

4 5 6 10 12 3 7 12 9

5 3 5 6 10 12 7 12 9

6 3 5 6 7 10 12 12 9

7 3 5 6 7 10 12 12 9

8 3 5 6 7 9 10 12 12

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:

lim ip Vectorul prelucrat u_inv

6 0 10 5 6 12 3 7 12 0

1 5 10 6 12 3 7 12 1

2 5 6 10 12 3 7 12 1

3 5 6 10 12 3 7 12 3

4 5 6 10 3 12 7 12 4

5 5 6 10 3 7 12 12 4

4 0 5 6 10 3 7 12 12 0

1 5 6 10 3 7 12 12 0

2 5 6 10 3 7 12 12 2

3 5 6 3 10 7 12 12 3

3 0 5 6 3 7 10 12 12 0

1 5 6 3 7 10 12 12 1

2 5 3 6 7 10 12 12 1

1 0 5 3 6 7 10 12 12 0

0 3 5 6 7 10 12 12

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.