Sortarea prin interclasare.

Search:

Algoritmi.

Prezentarea algorimului de sortare prin interclasare (bubble sort).

Cuprins:
1. Definirea sortarii prin interclasare.
2. Principiul de functionarea a algoritmului de sortare prin interclasare.
3. Analiza algoritmului de sortare prin interclasare.
4. Prevenirea greselilor de implementare a algoritmului de sortare prin interclasare.
5. Compararea sortarii prin interclasare cu alte tipuri de sortari.

1. Definirea sortarii prin interclasare. >>>

In domeniul calculatoarelor, sortarea prin interclasare este un algoritm de sortare care face parte din familia algoritmilor care se executa intr-o perioada de timp definita prin relatia O(n log n).Algoritmul de sortare prin interclasare este usor de inplementat deoarece este un algoritm de sortare stabil, in sensul ca el pastreaza ordinea de intrare a termenilor cu valori egale pana cand se termina procesul de sortare.Metoda sortarii prin interclasare este un exemplu de algoritm care functioneaza dupa principiul "imparte si stapaneste" (divide et impera), insa algoritmul acestei metode de sortare are la baza principiul de sortare a elementelor prin comparare.Acest algoritm de sortare prin interclasare a fost iventat de catre John von Neumann in anul 1945.

2. Functionarea algoritmului de sortare prin interclasare. >>>

Din punct de vedere conceptual, algoritmul de sortare prin interclasare functioneaza dupa acest procedeu:

1. Imparte lista catre terbuie sortata in doua sub-liste de dimensiuni egale.
2. Sorteaza recursiv fiecare dintre cele doua sub-liste pana cand acestea au dimensiunea 1.3. Grupeaza (interclaseaza) cele doua sub-liste sortate intr-o singura lista finala sortata.

Astfel ca sortarea prin interclasare detine doua strategii de sortare pentru a sorta datele aflate in orice structura de date:

1. Intotdeauna se vor executa mai putine treceri intr-o lista de dimesiuni mici care trebuie sortata, insa este valabila si cazul contrar cand pentru a sorta o lista de mari dimensiuni, atunci vor fi necesare mai multe treceri de sortare prin aceasta lista.
2. Intotdeauna se vor executa mai putini pasi pentru a construi o lista finala din doua sub-liste sortate de cat in cazul in care se lucreaza cu doua sub-liste nesortate, deoarece sub-listele care sunt sortate nu mai necesita un nou proces de sortare, caci algoritmul de sortare oricum le verifica din nou (acesta fiind un concept de baza), insa cum elementele sunt sortate deja rezulta ca algoritmul de sortare le parcurge foarte rapid, rezultand astfel un important castig de timp.

De exemplu: Se presupune utlizizerea algoritmului de sortare prin interclasare intr-o lista de numere intregi aflate intr-un tablou.

Presupunand ca se detine un tablou denumit A care are aranjate locatiile elementelor incepenad de la A1 pana la A2.Prima data algoritmul de sortare se va aplica asupa elementelor cuprinse in sublista care contine elementele A(A1...A Centru) si apoi in sublista care contine elementele A(A Centru+1...A2), un A Centru este partea intreaga de la (A1+A2)/2.Cand cele doua sub-liste ale tabloului a sunt regrupate intr-o singura lista, atunci procesul de sortare s-a terminat iar lista de valori intregi a tabloului A este sortata rezultand astfel un tablou sortat.

O simpla forma a reprezentarii algoritmului de sortare prin interclasare in pseudocod:

function SortareInterclasare(m)var lista stanga, dreapta, rezultat
if lungime(m) = 1return m
elsemijloc = lungime(m) / 2for fiecare x din m aflat inaintea lui mijlocmuta x la stanga
for fiecare x din m aflat dupa mijlocadd x to right
stanga = SortareInterclasare(stanga)
dreapta = SortareInterclasare(dreapta)
rezultat = SortareInterclasare(stanga, dreapta)
return rezultat

O alta reprezentare mai simpla a algoritmului de sortare prin interclasare:

function interclasare(stanga, dreapta)var lista rezultat
while lengime(stanga) > 0 and lungime(dreapta) > 0if primul_din(stanga) = primul_din(dreapta)verifica primul(stanga) pentru rezultat
stanga = restul_din(stanga)
elseverifica primul_din(dreapta) pentru rezultat
dreapta = restul_din(dreapta)
if lungime(stanga) > 0verifica restul_din(stanga) pentru rezultat
if lungime(dreapta) > 0verifica restul_din(dreapta) pentru resultat
return rezultat

3. Analiza algoritmului de sortare prin interclasare. >>>

Pentru a sorta un numar de n elemente sortarea prin interclasare prezinta o comportare multumitoare sau ineficienta reprezentata pri relatia O(n log n).Daca se aplica sortarea prin interclasare in cadrul unei liste de lungime n atunci timpul de sortare a acesteia va fi de T(n), unde relatia T(n)= 2T(n/2) + n provinde de la idea de baza a algoritmului aceastui tip de sortare.Adica, perioada de sortare T(n) a unei liste de dimensiune n depinde si de perioada de sortare a celor doua sub-liste: T(n)= 2T(n/2), plus numar de treceri pentru a sorta cele doua sub-liste rezultate: T(n)= 2T(n/2) + n.

In cazul in care sortarea prin interclasare se comporta ineficient aceasta va efectua un numar de (n|lg n| - 2^{|lg
n|} + 1) comparatii, care se cuprin in intervalul (n lg n- n+1) si (n lg n + n + O(lgn)). Astfel ca in cazul in care sortarea prin interclasare se comporta ineficient, se efectueaza cu 39% mai putine comparatii ale elementelor decat in cazul comportarii multumitoare a sortarii rapide, deaoreace sortarea prin interclasarea va efectua intotdeauna mai putine comparatii decat cel rapid algoritm de sortare - sortarea rapida (quicksort), exceptie facand cazurile extrem de rare cand comportarea ineficienta a sortarea prin interclasare este mai performanta decat comportarea eficienta a sortarii rapide.Sortarea prin interclasare cat si sortarea rapida pot sorta si cazuri mai complexe, ambele finalizand sortarea intr-un timp definit prin relatia O(n log n).

Implementarile recursive ale algoritmului de sortare prin interclasare efectueaza printr-un numar de 2n-1 treceri in cazul in care acesta se comporta ineficient, care in comparatie cu sortarea rapida care efecuteaza un numar de n treceri, aceqasta insemnand ca sortarea prin interclasare este mult mai recursiva decat sortarea rapida.Oricum chiar daca sortarea prin interclasare este iterativa,non-iterativa, implementarile acestei sortari ocolesc metoda de efectuare a mai multor treceri decat este necesar, astfel find usor de implementat.Cele mai multe implementari ale sortarii prin interclasare nu efectueaza sortari "pe loc", astfel ca capacitatea memoriei alocata la inceputul procedeului de sortare are aceeasi dimensiune ca si capacitatea memoriei folosita pentru a stoca datele si dupa terminarea procesului de sortare.Deasemeni este permisa utilizarea conceptului de sortare pe loc in cadrul algoritmului de sortare prin interclasare, insa va rezulta un algoritm foarte complicat care va avea o performanta foarte scazuta din puncrt de vedere practic, astfel ca algoritmul nu va mai rula intr-un timp de O(n logn).In acest caz sortarea prin ansamble (heapsort) are o comportare mult mai eficienta, deoarece prezinta un algoritm mai usor de implemetat.

sortaerea prin interclasare este mult mai eficienta decat sortarea rapida in cazul in care se lucreaza cu unele tipuri de liste care trebuiesc sortate, si care pentru a fi accesate trebuie sa se execute un acces segvential.Unele limbaje de programare cum este de exemplu Lisp functiioneaza foarte eficient cu astfel de tipuri de liste, caci are la baza conceptul de accesare segventiala a listelor.Desii sortarea prin interclasare este mai putin utilizata decat sortarea rapida, totusi prezinta un algoritm de sortare stabil deoarece operatiile de interclasare sunt implementate separat.

4. Prevenirea greselilor de implementare a sortarii prin interclasare. >>>

O greseala care se intalneste in cela mai multe implementari ale algoritmului de sortare prin interclasare este impartirea listei de locatii ale elementelor in doua sub-liste.Astefel ca se poate intampla ca determinarea locatiei de mijloc sa nu se alfe in lista locatiilor ca si inrmatorul exemplu:

function interclasare(int stanga, int dreapta)
{if (stanga < dreapta) {int mijloc = (stanga + dreapta) / 2;
[...]

Astfel ca algoritmul prezentat mai sus se poate comporta eficient in unele cazuri, insa daca se lucreaza cu liste de mari dimensiuni poate efectua operatii gresite din punct de vedere al sortarii.Astfel, din adunarea elementelor "stanga" si dreapta" ar putea rezulta o valoarea de tip interg care sa dfepaseasca capacitatea memoriei utilizate de catre algoritm rezultand astfel o impartire complet gresita a listei ce trebuie sortata.Aceasta problema poate fi ocolita daca se implica in calcul si numarul de locatii a memoriei autilizate de catre algoritmul de sortare.

int middle = left + ((right - left) / 2);

5. Compararea algoritmului de sortare prin interclasare cu alti algoritmi de sortare. >>>

Desii sortarea prin interclasare prezinta aceasi limita a perioadei de sortare ca si sortarea prin ansamble (heapsort), sortarea prin ansamble necesita un spatiu de memorie de È(1) locatii, iar sortarea prin interclasare necesita un numar de È(n) locatii de memorie, si din aceasta cauza sortara prin ansamble este unul din cei mai utlizati algoritmi deoarece se comporta eficient in implementarile practice.Sortarea rapida este considerat cel mai rapid algorimt de sortare,iar timpul de a rezolva sortari complexe este de O(n logn), insa performanta acestia scade drastic daca nu se aleg pivotii corespunzatori.In acest caz sortarea rapida este de patru ori mai lenta decat sortara prin interclasare cand se comporta ineficient.Un avantaj pentru sortarea prin interclasare este stabilitatea, operatiilr care se executa in paralel sunt independente, si este mult mai efeicient in lucrul cu componentele segventiale care proces lent de accesare.Sortarea prin interclasare se comporta cel mai bine in lucrul cu liste inlantuite, caci in cadrul acestora este simplu de implementat, si necesita un spatiu suplimentar de memorie de numai È(1), insa nu taota metodele de sortare au o asemenea performanta in lucrul cu liste inlantuite: de exemplu sortarea rapida se comporta ineficient, iar pentru algoritmul sortarii prin ansamble este imposibil de a realiza o performanta ca si sortarea pin interclasare in lucrul cu listele inlantuite.

In cadrul limbajul de programare Perl 5.8 sortarea prin interclasare reprezinta algoritmul de sortare care continua procesul de sortare al algoritmului de sortare principal, in cazul in care acest algoritm principal (care poate fi sortarea rapida - caci este utilizat si in versiunile anterioare ale acestui limbaj de programare) prezinta deficiente.In limbajul Java, metoda numita Arrays.sort() utilizeaza sortarea prin interclasare sau un algoritm de sortare rapida imbunatatita pentru a putea lucra eficient cu mai multe tipuri de date, acesta din urma inlcuind algoritmul de sortare prin insertie care avea un proces de sortare foarte lent pentru sortarea tablourilor.

Inapoi la pagina principala