1. Definirea sortarii prin selectie. >>>
Sortarea prin selectie este un algoritm de sortare,
si a carui principiu de functionare este specific algoritmilor de sortare prin comparare care se fac "pe loc".Acest tip de sortare are complexitatea O(n2), si se comporta eficient daca lucreaza cu liste mari de date, iar in cazul in care se comporta ineficient algoritmul are o rapiditate de sortare asemanatoare cu rapiditatea algoritmului de sortare ineficienta al metodei de sortare prin insertie.Sortarea prin selectie este preferata in practica deoarece reprezinta un algoritm simplu, avand si alte avantaje performante rezultand astfel ca sortarea prin selectie se situeaza deasupra altor algoritmi complicati de sortare chiar daca se sorteaza structuri de date de aceeasi complexitate.Sortarea prin selectie functioneaza dupa urmatorul principiu: 1. Se cauta elementul cu cea mai mica valoare din lista.
2. Daca pe prima pozitie in lista exista o alta valoare mai mare decat valoarea cea mai mica din tablou, atunci aceasta se inlocuieste cu o noua valoare mica, pana cand o valoare si mai mica decat ea prezenta in lista, o va inlocui.
3. Se repeta pasii descrisi mai sus pentru restul listei ramasa nesortata (incepand de la pozitia a doua, si tot asa.)
Iata un exemplu al celor trei pasi descrisi mai sus:
31 25 12 22 11
11 25 12 22 31
11 12 25 22 31
11 12 22 25 31
Explicarea principiul acestei metodede sortare implementata in limbajul Pascal este:
Pentru fiecare pozitie i, incepand cu prima, se selecteaza din subsirul ce incepe cu acea pozitie cel mai mic element si se amplaseaza pe locul respectiv prin interschimbare cu elementul curent de pe pozitia i) Structura generala a algoritmului este:
selectie(x[1..n])
for i<-1,n-1 DO < se determina valoarea minima din x[i..n] si se interschimba cu x[i] >
Ciclul for continua pana la n-1 deoarece subsirul x[n..n] contine un singur element care este plasat chiar pe pozitia potrivita, ca urmare a interschimbarilor efectuate anterior.
Descrierea detaliata a algoritmului este: selectie(x[1..n])
for i <- 1,n-1 do k <-i { indicele curent al minimului }
for j <- i+ 1,n do { ciclu pentru cautarea minimului }
if x[k] > x[j] THEN k <- j { noul indice al minimului }
if k= i THEN x[k] x[i] { plasarea minimului pe pozitia adecvata } RETURN(x[1..n])Verificarea corectitudinii. Aratam ca un invariant al ciclului exterior (dupa i) este: { x[1..i - 1] este ordonat crescator si x[i-1] < x[j] pentru j = i,n}. La inceput i= 1 deci x[1..0] este sir vid. Ciclul for interior (dupa j) determina valoarea minima din x[i..n]. Aceasta este plasata prin interschimbare pe pozitia i. Se obtine astfel ca x[1..i] este ordonat crescator si ca x[i] < = x[j pentru j = i + 1,n. Dupa incrementarea lui i (la sfarsitul ciclului dupa i) se reobtine proprietatea invarianta. La final i = n , iar invariantul conduce la x[1..n -1] crescator si x[n-1] < = x[n] adica x[1..n] crescator.
Algoritmul este partial natural (numarul de comparatii nu depinde de gradul de sortare alsirului).In varianta prezentata (cand minimul este interschimbat cu pozitia curenta) algoritmul nu este stabil. Daca insa in locul unei singure interschimbari s-ar realiza deplasarea elementelor subtabloului x[i..k - 1] la dreapta cu o pozitie (ca in algoritmul insertiei) iar x[k] (salvat in prealabil intr-o variabila auxiliara) s-ar transfera in x[i] algoritmul ar deveni stabil.
2. Implementarea. >>>
Mai jos este prezentat o implementare a sortarii prin selectie in limbajul C, care utilizeaza o functie de inlocuire: void selectionSort(int a[], int size)
{ int i, j, min;
for (i = 0; i < size - 1; i++){min = i;
for (j = i+1; j < size; j++)swap(a[i], a[min]); } }
3. Analiza sortarii prin selectie. >>>
Sortarea prin selectie este un procedeu simplu de analizare (comparare), care in comparatie cu alti algoritmi de sortare acesta nu depinde de datele aflate in tablou.Selectarea elementului cu valoarea cea mai mica valoare aflata intr-un tablou cu n elemente presupune o verificare a tuturor celor n elemente (aceasta realizand n-1 comparatii), si apoi pozitionarea lor in locurile potrivite.Gasirea urmatorului element cu valoarea cea mai mica necesita verificare celor n-1 elemente ramase nesortate si asa mai departe,iar insumant numarul de treceri de sortare in functie de pozitia elementului: (n - 1) + (n - 2) + ... + 2 + 1 = È(n2) comparatii.Fiecare dintre aceste verificari necesita o singura inlocuire pentru un total de n-1 inlocuiri (elementul final este deja sortat).Prin numarul de treceri si comparatii se determina timpul de rulare al algoritmului, care este È(n2).
4. O comparatie cu alti algoritmi de sortare. >>>
Desii este un algoritm simplu si chiar daca face parte din familia algoritmilor care au un numar de verificari de È(n2), sortarea prin selectie intotdeauna va fi mult mai performanta deacat sortarea prin interschimbare sau sortarea "gnome", insa in general este mai putin performanta deacat sortarea prin insertie.Sortarea prin insertie este foarte asemanatoare cu sortarea prin selectie in sensul ca dupa k iteratii rezulta ca primele k elemente sunt sortate in ordine crescatoare.Avantajul sortarii prin insertie este ca ea verifica mai multe elemente decat este necesar pentru a pozitiona in ordine elementul k+1, insa sortarea prin selectie trebuie sa verifice toate elementele ramase nesortate pentru a gasii elementul k+1.
Un simplu calcul indica faptul ca aceasta sortare prin insertie de obicei implica mai multe comparatii decat sortarea prin selectie in cazul in care se folosesc termeni cu valori egale, astfel ca sortarea prin insertie poate poate acorda mai multa sau mai putina atentie ordinii elementelor din tabloul ce trebuie sortat.Aceasta poate fi privit ca un avantaj in cadrul aplicatiilor in timp real caci sortarea prin selectie nu se bazeaza pe ordinea elementelor din tablou, desii aceasta ar puta influenta timpul de rulare al algorimului de sortare prin insertie determinand o sortare efectuata intr-un interval de timp variabil.Oricum, acesta este mai mult decat un avantaj pentru sortarea prin insertie, deoarece aceasta ruleaza mult mai eficient daca tabloul este deja sortat.
O alta diferenta este aceea ca sortare prin selectie intotdeauna va realiza È(n) inlocuiri, insa sortarea prin insertie realizeaza È(n2) inlocuiri in cazul in care aceasta se comporta ineficient sau multumitor.Deoarece inlocuirile elementelor in procesul de sortare presupune memorarea tabloului in memorie, atunci sortarea prin selectie este prefereta daca scrierea in memorie este semnificativ mult mai expansiva decat citirea din memorie, astfel ca se obtin performante si mai bune daca se sorteaza un tablouaflat in memoria EEPROM sau Flash.
Concluzionand putem remarca faptul caci sortarea prin selectie se comporta foarte ineficient in cadrul tablourile mari de date, fiind mai puti performanta in comparatie cu algorimii de tip "divide et impera" cum este sortarea rapida si sortarea prin interclasare.Oricum, sortarea prin insertie si sortarea prin selectie realizeaza de obicei o perioada de sortare foarte rapida daca se sorteaza tabloul care contin mai putin de 10-20 elemente.
5. Variante ale sortarii perin selectie. >>>
Sortarea prin ansamble (heapsort) improvizeaza algoritmul sortarii prin selectie prin folosirea unei structuri de date inplicite in ansamblu pentru a accelera procesul de gasire sau inlocuire a elementelor aflata la baza strcturilor de date utilizate.Daca este implementata corect, ansamblul va perimte gasirea urmatorului element cu valoarea cea mai mica intr-un interval de timp determinat timp prin È(log n) comparativ cu intervalul de timp È(n) pentru sortarea prin selectie obisnuita, reducand astfel timpul de sortare la un timp de de È(nlogn).
O varianta bidirectionala a sortarii prin selectie este denumita in termenul englez "cocktail sort", care poate fi definita cau un algoritm care gaseste limitele listei prin determinarea celei mai mari valori si celei mai mici valori la fiecare trecere de sortare.Aceasta reduce numarul de verificari ale elementelor din lista cu un factor de 2, eliminand unele bucle (cicluri) de sortare fara a influenta numarul de comparatii sau inlocuiri."Cocktail sort" este mult mai eficienta si in comparatie cu o alta varianta de sortare bidirectionala numite sortare prin interschimbare.
6. Exemplu de algoritm care implententeaza sortarile prin insertie,interschimbare,selectie. >>>
#include
#include
#include
#include
#include
void sortare_interschimbare(int a1[])
{int i,j,temp;
for(i=0;i<10;i++)
{for(j=0;j{if(a1[j]>a1[i]) //sortare crescatoare
//if(a1[i]>a1[j]) sortare descrescatoare
{int temp=a1[i]; //inlocuire
a1[i]=a1[j];
a1[j]=temp;
} } } }
void sortare_selectie(int a2[],int lungimea_tabloului2)//selection sort function
{int i,j,min,minat;
for(i=0;i<((lungimea_tabloului2)-1);i++)
{minat=i;
min=a2[i];
for(j=i+1;j<(lungimea_tabloului2);j++) //selecteaza mininmul din tabloul
{if(min>a2[j])
{minat=j; // pozitia elementului cu valoare minima
min=a2[j]; } }
int temp=a2[i] ;
a2[i]=a2[minat]; //inlocuire
a2[minat]=temp;
} }
void sortare_insertie(int a[], int lungimea_tabloului)
{int i, j, v;
for (i=0; i< lungimea_tabloului; i++)
{v = a[i];
j = i-1;
while ((j>=0) && (a[j]>v))
{} a[j+1] = v;
} }
void verificaDacaTabloul_a_EsteSortat (int tablou[], int lungimea_tabloului)
{int i;
for (i = 0; i < lungimea_tabloului; i+=1)
{if (tablou[i-1] > tablou[i])
{printf("\nTabloul a nu este sortat la pozitia %d", i-1);
} } }
int main()
{int j;
unsigned int i;
int a[] = {5,1,9,3,2,8,6,4,7,9};
int a1[] = {50,10,90,30,20,80,60,40,70,90};
int a2[]= {500,100,900,300,200,800,600,400,700,900};
sortare_insertie(a,sizeof(a)/sizeof(*a));
printf("\nSortare prin insertie: ");
for(i=0; i< sizeof(a)/sizeof(*a); i++) { printf(" %d ", a[i]); }
sortare_interschimbare(a1);
printf("\nsortarea prin interschimbare: ");
for(i=0; i< sizeof(a1)/sizeof(*a1); i++) { printf(" %d ", a1[i]); }
sortare_selectie(a2,sizeof(a2)/sizeof(*a2));
printf("\nSortarea prin selectie: ");
for(i=0; i< sizeof(a2)/sizeof(*a2); i++) { printf(" %d ", a2[i]); }
return 0; } |