Sortarea prin interschimbare.

Search:

Algoritmi.

Prezentarea algoritmului de sortare prin interschimbare (bubble sort).

Alege:
1. Despre sortarea prin interschimbare.
2. Analiza sortarii prin interschimbare.

2.1. Comportare ineficienta.
2.2. Comportare eficienta.
2.3. "Elementele-iepuri" si "elementele-cestoase".
2.4. Implementari alternative.
3. In practica.

1. Sortarea prin interschimbare. >>>

Sortarea prin interschimbare este un algoritm simplu de sortare, si a carui principiu de functionare consta prin parcurgerea repetata listei ce trebuie sortata, comparand cate doi termeni, care vor fi interschimbati daca se afla pe pozitii gresite.Deoarece este o metoda de sortare care lucreaza prin compararea elementelor, sortarea prin insertie face parte din familia metodelor de sortare prin comparare. Trecerile prin lista ce trebuie sortata se executa repetat pana cand nu se mai executa interschimbari, prin aceasta intelegandu-se ca lista este sortata.

Un mod simplu de a explica o metoda de sortare prin interschimbare in pseudo cod este urmatorul:

procedure sortareInterschimbare( A: lista termenilor ce trebuiesc sortati) defined as:dointerschimbarea := false
for each i in 0 to length( A ) - 2 do:if A[ i ] > A[ i + 1 ] theninterschimba( A[ i ], A[ i + 1 ] )
interschimbarea := true
end if
end for while interschimbare
end procedure

Un alt mod de a exprima algoritmul de mai sus este:

for i <- 1 to length[A]do for j <- length[A] downto i + 1 do if A[j] < A[j-1]
then exchange A[j] <-> A[j-1]

2. Analizarea procedeului de sortare prin interschimbare.

2.1. Performanta ineficienta. >>>
Sortarea prin interschimbare are un grad de complexitate descris O(n²) intr-o lista de dimensiune n.Adica, fiecare element nu este mutat mai mult decat o pozitie la fiecare trecere a metodei de sortare.Nu exista elemente care sortate prin metoda interschimbarii care sa se afla la o pozitie mai mare deacat n-1 fata de ultima locatie detinuta, astfel ca se vor efectua cel mult n-1 operatii pentru a muta un element la pozitia lui finala, si nici nu se va utiliza un numar de operatii mai mare decat (n-1)² =O(n²).

In cazul in care intr-o lista care trebuie sortata elementul cu valoarea cea mai mare se afla in partea inferioara (baza) listei, fiecare trecere a metodei de sortare prin lista va muta acest element cu o singura pozitie catre varful listei, astfel executandu-se n-1 treceri pentru a muta acest element in pozitia sortata finala.Fiecare trecere care parcurge lista nesortata va executa un numar de n-1 operatii, care in cazul unei comportari ineficienta va fi de Ù(n²).

2.2. Comportare eficienta. >>>
Cand algoritmul sortarii prin interschimbare se aplica unei liste sortate, algoritmul va verifica elementele listei, si daca nu se interschimba pozitia niciunui element atunci se va intelege ca lista este sortata.In cest caz metoda sortarii prin interschimbare se va efectua intr-un timp de O(n), numai daca lista este complet sortata.Deasemeni se va utiliza si un timp redus semnificativ daca elementele dintr-o lista nesortata nu sunt prea departe de pozitia lor corecta.

2.3. "Elementele-iepuri" si "elementele-cestoase". >>>
Pozitia elementelor in cadrul sortarii prin interschimbare are un rol important, si influenteaza performanta algoritmului.Elementele care contin valori mari pozitionate in varful listei nu reprezinta o problema, caci ele pot fi rapid mutate la baza listei in locatia potrivita.Elementele care au valori mici pozitionate la baza listei au o miscare de pozitionare mai lenta, deoarece valorile lor pot fi apropriate þi trebuiesc comparate foarte des unele cu altele.Acesta ar fi motivul pentru care au fost denumite elementele-cestoase (adica au valori mici si au un proces de pozitionare foarte lent) si elementele-iepuri (care au valori mari si pot fi rapid pozitionate).

Au fost facute multe incercari de a elimina efectul elementelor-cestoase, si s-a incercat accelerarea procesului lor de pozitionare.Astfel a fost implementata metoda sortarii prin interclasare care se comporta relativ eficient, insa retine totusi o complexitate de O(n²) in cazul in care algoritmul se comporta ineficient.Sortarea prin combinare este un alt procedeu de al elimina "cestoasele" a carui procedeu consta in compararea elementelor cu valori mari in paralel cu un alt procedeu care compara elementele cu valori mici, rezultant astfel un castig semnificativ de timp.

2.4. Implentari alternative. >>>
In cadrul metodei de sortare prin interschimbare, dupa fiecare trecere a metodei de sortare,elementele cu valori mari intotdeauna se vor pozitiona tot mai mult catre locul potrivit la baza listei.In timpul fiecarei comparatii, este clar ca aceste elemente cu valori mari nu vor urca catre varful listei daca valoarea elementului cu care a fost comparat are valoare mai mica.Presupunand ca se detine o lista cu n elemente, atunci al n^-lea element va fi intotdeauna la locul potrivit.Astfel se vor sorta si celelalte n-1 elemente ramase.Si din nou, al n-1^-lea element va fi la locul potrivit.

Reprezentat printr-un pseudocod principiul descris mai sus va fi astfel:

procedure bubbleSort( A : list of sortable items ) defined as:n := length( A )
n := length( A )
dointerschimbare := false
n := n - 1
for each iin 0 to n do:if A[ i ] > A[ i + 1 ] then
interschimba( A[ i ], A[ i + 1 ] )
interschimbare := true
end ifend for
while interschimbare
end procedure

Se poate efectua treceri de interschimbare in cadrul partiulor mici ale listei.Mai precis, pentru a efectua n² comparatii (si interschimbari), se poate folosii numai n + (n-1) + (n-2) +...+1 comparatii.Aceasta insumata devine n(n+1)/2, care este exact O(n²), insa care poate fi considerat rapid in practica.

3. In practica. >>>

Desii sortarea prin interschimbare este unul dintre cei mai simpli algoritmi, putand fi usor intelesi sau implementati, totusi are o complexitate de O(n²) care-l face prea ineficient pentru a sorta liste de dimensiuni mari.Oricum, desii este simplu, comparativ cu alti algoritmi care sunt cuprinsi care au complexitatea de O(n²), sortarea prin insertie este mult mai eficienta decat sortarea prin interschimbare.

Insa datorita complexitatii, sortarea prin interschimbare este utilizata adesea pentru a explica conceptul unui algoritm, sau a unui algoritm de sortare pentru studentii incepatori in domeniul calculatoarelor.

Sortarea prin interschimbare este din punct de vedere asimptotic echivaleanta cu sortarea prin insertie, cand aceasta din urma are un comportament ineficient, insa acesti doi algoritmi difera foarte mult la numarul de mutari necesare efectuate.Rezultatele experimentelor efectuate de unul dintre cercetatori algoritmilor de sortare Owen Astrachan, indica faptul ca sortarea prin insertie se comporta mult mai eficient in liste nesortate.Din aceste motive unele baze de date moderne ocolesc utilizarea sortarii prin interschimbare in favoarea sortarii prin insertie.

Deasemeni sortarea prin interschimbare se comporta ineficient si in cadrul microprocesoarelor, deoarece necesita multe instructiuni si multe accese la memorie in comparatie cu sortarea prin insertie.Experimentele lui Astrachan realizate prin sortarea sirurilor de caractere in Java au demonstrat ca sortarea prin interschimbare este mult mai inceata decat sortarea prin insertie si 40% mai lenta decat sortarea prin selectie.

Inapoi la pagina principala