I. Ordonarea unui sir - Metoda "bulelor" (Bubble Sort)

Se citeste un sir de numere intregi si se cere sa se ordoneze elementele acestui sir crescator

A: 7 , 4 , 5 , 3 , 9 , 1 (inainte)

A: 1 , 3 , 4 , 5 , 7 , 9 (dupa)

Ideea care sta la baza acestei metode este urmatoarea: se parcurge sirul, comparandu-se elementele consecutive din sir doua cate doua. Daca acestea nu sant in relatia dorita ("³" sau "£") se schimba valorile elemntelor.

Printr-o parcurgere a sirului si efectuarea comparatiilor obtinem:   

Comparam A[i] > A[i+1] daca da, le schimb

Se observa ca, dupa o parcurgere a vectorului, sirul obtinut nu este ordonat deci este necesara reluarea procedeului descris anterior.

Daca vectorul contine elemente deja ordonate se face o singura parcurgere. La efectuarea unei interschimbari se marcheaza aceasta operatie prin valoarea "FALSE" a unei variabile logice care, inainte de parcurgere va avea valoarea "TRUE". La sfarsitul algoritmului valoarea acestei variabile va fi "TRUE" , pentru ca nu va mai fi necesara nici o interschimbare.

NU DA

			aux := a[i]

NU

pentru i := 1 la n

PROGRAM BULE;

TYPE

vector = ARRAY[1..100] OF integer;

VAR

a : vector;

n , i , aux : integer;

ordonat : boolean;

BEGIN

Write ('nr de componente= ');readln(n);

FOR i := 1 TO n DO BEGIN

write ('a[', i ,']= ');

readln( a[i] );

END;

FOR i := 1 TO n DO

write (a[ i ],' ');

writeln;

REPEAT

ordonat := true;

FOR i := 1 TO n-1 DO

IF a[i] > a[i+1] THEN BEGIN

aux := a[i];

a[i] := a[i+1];

a[i+1] := aux;

ordonat := false;

END;

UNTIL ordonat = true;

FOR i := 1 TO n DO

write (a[ i ], ' ');

writeln;

END.

2. Metoda de sortare prin INSERTIE

consta in inserarea fiecarui element al vectorului la locul corespunzator in raport cu elementele sortate anterior. Principiul de baza al algoritmului de sortare prin insertie este urmatorul:

Se presupune ca subsecventa a[1], a[2], . , a[i-1] este sortata; Se cauta in aceasta subsecventa locul j al elementului a[i] si se insereaza a[i] pe pozitia j. Sa vedem cum se determina pozitia j (finala in vectorul sortat):

j = 1 daca a[i] < a

1 < j < i si sunt satisfacute relatiile a[j-1] <= a[i] < a[j]

j = i daca a[i] >= a[i-1]

Determinarea lui j se face prin cautare secventiala sau prin cautare binara. Putem observa ca aceasta tehnica de sortare se bazeaza pe metoda jucatorului de bridge

Implementare: Consideram cazul cand pozitia j este determinata prin cautare secvetiala (de la dreapta la stanga) simultan cu deplasarea elementelor mai mari ca a[i] cu o pozitie la dreapta. Aceasta deplasare se realizeaza prin interschimbari astfel incat valoarea a[i] realizeaza o deplasare la stanga pana ajunge la locul ei final.

PROGRAM Sort_Ins;

VAR a:array[1..50] of integer;

n, i, j, k, aux: integer;

BEGIN

Write('cate elem are vectorul: '); readln(n);

Writeln('Introduceti elem:');

FOR i := 1 TO n DO BEGIN

Write('a[', i ,']= '); Readln(a[i]);

END;

FOR i := 2 TO n DO begin

j := i - 1;

aux := a[i];

WHILE (j>=1) AND (a[j]>aux) DO j := j - 1;

FOR k := i DOWNTO j+1 DO a[k] := a[k-1];

a[j+1] := aux;

end;

FOR i :=1 TO n DO write(a[i],' ');

END.   

3. Metoda de sortare prin SELECTIE

consta in determinarea elementului minim si aducerea lui pe prima pozitie; apoi dintre elementele ramase in vector, se determina minimul si va fi adus pe a 2-a pozitie, s.a.m.d. pana cand toate elementele vor fi asezate in ordine.

Implementare: Vectorul se parcurge de la prima pozitie pana la pozitia n-1; se compara fiecare element de la pozitia 1 pana la pozitia n-1 cu elementele aflate dupa el. Daca elementele nu sunt in ordinea corecta, se efectueaza interschimbarea acestora, astfel incat minimul se determina comparand un element cu toate elementele care ii succed.

Algoritmul Sort_Sel;

FOR i := 1 TO n-1 DO

FOR j := i+1 TO n DO

IF a[i] > a[j] THEN begin

aux := a[i];

a[i] := a[j];

a[j] := aux;

end;

4. Metoda de sortare prin NUMARARE

Fie vectorul a = (a₁, a₂, . , a_n).

Pentru fiecare element se numara cate elemente sunt mai mici decat el. Numerele pe care le obtinem se vor memora intr-un vector k = (k₁, k₂, . , k_n).

Pentru a obtine elementele sortate, pe baza elementelor vectorului k, vom rearanja elementele vectorului a intr-un vector b = (b₁, b₂, . , b_n), unde b[k[i]+1] = a[i].

EX:

N=5, a=(7, 6, 3, 8, 0)

Initial: k = (0, 0, 0, 0, 0)

Iterativ: k = (3, 2, 1, 4, 0)

k = (0, 3, 6, 7, 8)

Procedeul: Pentru fiecare element incepand de la pozitia 2, se compara valoarea acestuia cu valorile aflate in vectorul a, inaintea sa. Daca elementul curent este mai mic decat un anumit element aflat inaintea sa, atunci se contorizeaza numarul de elemente mai mici pentru elementul care este mai mare, marindu-se cu o unitate acest contor; in caz contrar acesta se modifica pentru numarul curent.

Algoritmul Sort_Number;

FOR i := 1 TO n DO k[i] := 0;

For i := 2 TO n DO

FOR j := 1 To i-1 DO

IF a[i] < a[j] THEN k[j] := k[j]+1

ELSE k[i] := k[i]+1;

FOR i :=1 TO n DO b[k[i]+1] := a[i];

FOR i := 1 TO n DO write (b[i],' ');

Problema: Se considera un vector cu n elemente, ordonat crescator si un numar intreg x. Sa se insereze x in vectorul dat astfel incat acesta sa ramana ordonat.