Sortarea prin selectie

Sortarea prin selectie

Sortarea prin selectie foloseste procedeul de a selecta elementul cu cheia minima si de a schimba intre ele pozitia acestui element cu cea a primului element.

Se repeta acest procedeu cu cele n -1 elemente ramase, apoi cu cele n -2, etc., terminand cu ultimele doua elemente.

Aceasta metoda este oarecum opusa sortarii prin insertie care presupune la fiecare pas un singur element al secventei sursa si toate elementele secventei destinatie in care se cauta de fapt locul de insertie.

Selectia in schimb presupune toate elementele secventei sursa dintre care selecteaza pe cel cu cheia cea mai mica si il depoziteaza ca element urmator al secventei destinatie.

SortarePrinSelectie

FOR (n -1 iteratii)

1 atribuire

FOR (i -1 iteratii)  

H_m -1 atribuiri

1 comparatie

1 atribuire

2 atribuiri

Fig.3.2.2.a. Profilul temporal al sortarii prin selectie

Select 1(char *s, int n)

t=s[j];}

S[k]=s[i]; s[i]=k;}}

Analiza sortarii prin selectie

Numarul comparatiilor de chei C este independent de ordinea initiala a cheilor.

[3.2.2.c]

Numarul atribuirilor este de cel putin 3 pentru fiecare valoare a lui i, (temp:= a[i],a[min]:= a[i],a[i]:= temp), de unde rezulta:

[3.2.2.d]

Acest minim poate fi atins efectiv, daca initial cheile sunt deja sortate.

Pe de alta parte daca cheile sunt initial in ordine inversa M_max se determina cu ajutorul formulei empirice [3.2.2.e] [Wi76].

(1) [3.2.2.e]

Valoarea medie a lui M nu este media aritmetica a lui M_min si M_max , ea obtinandu-se printr-un rationament probabilistic in felul urmator.

Se considera o secventa de m chei.

Fie o permutare oarecare a celor m chei notata cu k₁ , k₂ , , k_m.

Se determina numarul termenilor k_j avand proprietatea de a fi mai mici decat toti termenii precedenti k₁ , k₂ , ,.k_j-1.

Se aduna toate valorile obtinute pentru cele m! permutari posibile si se imparte suma la m!

Se demonstreaza ca rezultatul acestui calcul este H_m-1, unde H_m este suma partiala a seriei armonice [3.2.2.f][Wi76]: