Sortarea prin interschimbare

Sortarea prin interschimbare

Clasificarea metodelor de sortare in diferite familii ca insertie, interschimbare sau selectie nu este intotdeauna foarte bine definita.

Paragrafele anterioare au analizat algoritmi care desi implementeaza insertia sau selectia, se bazeaza pe fapt pe interschimbare.

In acest paragraf se prezinta o metoda de sortare in care interschimbarea a doua elemente este caracteristica dominanta.

Principiul de baza al acestei metode este urmatorul: se compara si se interschimba perechile de elemente alaturate, pana cand toate elementele sunt sortate.

Ca si la celelalte metode, se realizeaza treceri repetate prin tablou, de la capat spre inceput, de fiecare data deplasand cel mai mic element al multimii ramase spre capatul din stanga al tabloului.

Daca se considera tabloul in pozitie verticala si se asimileaza elementele sale cu niste bule de aer in interiorul unui lichid, fiecare bula avand o greutate proportionala cu valoarea cheii, atunci fiecare trecere prin tablou se soldeaza cu ascensiunea unei bule la nivelul specific de greutate.

Din acest motiv aceasta metoda de sortare este cunoscuta in literatura sub denumirea de bubblesort (sortare prin metoda bulelor).

In multe cazuri ordonarea se termina inainte de a se parcurge toate iteratiile buclei FOR exterioare.

In acest caz, restul iteratiilor sunt fara efect, deoarece elementele sunt deja ordonate.

O modalitate evidenta de imbunatatire a algoritmului bazata pe aceasta observatie este aceea prin care se memoreaza daca a avut sau nu loc vreo interschimbare in cursul unei treceri.