SELECTION SORT
ALGORITMO:
pos:=0;
for i:=1 to n-1 do
begin
min:=a[i];
for j:=(i+1) to n do
begin
if a[j] < min then
begin
min:=a[j];
pos:=j;
end;
end;
aus:=a[i];
a[i]:=min;
a[pos]:=aus;
end;
SPIEGAZIONE ALGORTIMO
Il Selection Sort opera in modo simile all’ordinamento ingenuo, con la differenza che, prima di effettuare lo scambio, trova il minimo valore con il quale effettuare lo scambio. Il ciclo interno è quindi un semplice test per confrontare l'elemento corrente con il minimo elemento trovato fino a quel momento. Lo spostamento degli elementi è fuori dal ciclo interno: ogni scambio pone un elemento nella sua posizione finale quindi il numero di scambi è pari a n − 1 (dato che l'ultimo elemento non deve essere scambiato).
COMPLESSITA’
Il tempo di calcolo è determinato dal numero di confronti.
L'ordinamento per selezione effettua circa
\frac{n^2}{2} confronti ed n scambi.
La complessità di tale algoritmo è dell'ordine di
\frac{n(n-1)}{2} = \frac{n^2 - n}{2} = O(n^2)
Torna a Programmazione e Lab.
Non ci sono commenti in questa pagina. [Scrivi commento]