|
Selection Sort |
   |
|
|
Utilizzando l'algoritmo per la posizione del minimo si può individuare il minimo e scambiarlo con il valore in 1° posizione. Si ripete l'operazione con il sottovettore con indice da 2 a N, da 3 a N, ... e ogni elemento andrà al posto che gli spetta. Procedure SELESORT_1(var V: Vettore; N: Integer);
var
PosMin, i, j: Integer;
begin
for i:=1 to N-1 do
begin
PosMin:=i;
for j:=i+1 to N do
if(V[j] < V[PosMin]) then
PosMin:=j;
SCAMBIA(V[i], V[PosMin]);
end;
end;
Rispetto al bubble sort l'elemento scambiato occuperà definitivamente la posizione i-esima: il numero di scambi? (N-1). EsempioV={40, 35, 20, 15}, i=1, j=2..4 --> PosMin=4, V={15, 35, 20, 40}V={15, 35, 20, 40}, i=2, j=3..4 --> PosMin=3, V={15, 20, 35, 40}V={15, 20, 35, 40}, i=3, j=4..4 --> PosMin=3, V={15, 20, 35, 40}
Si può diminuire il numero di scambi, a scapito di un if()then aggiuntivo... Procedure SELESORT_2(var V: Vettore; N: Integer);
var
PosMin, i, j: Integer;
begin
for i:=1 to N-1 do
begin
PosMin:=i;
for j:=i+1 to N do
if(V[j] < V[PosMin]) then
PosMin:=j;
if(PosMin <> i) then
SCAMBIA(V[i], V[PosMin]);
end;
end; |
|
