Selection sort: differenze tra le versioni

Versione delle 15:57, 30 set 2007

Versione delle 18:58, 13 nov 2007

Riga 14:

=== [[C (linguaggio)|C]] ===

<source lang="C">

<nowiki>

void selection(double a[], unsigned long N) {

int i, j, min;

int i, j,double mint;

double t;

for (i=0; i < N-1; i++) {

min = i;

for (j= i + 1; j < N; j++)

if (a[j] < a[min])

min = j;

t = a[min];

Riga 31 ⟶ 30:

}

}

</nowikisource>

<!--

====Implementazione Alternativa====

<nowiki>

void selection(double a[], unsigned long N) {

int i, j;

double t;

int i, j;

double t;

for (i=0; i < N-1; i++) {

Riga 49 ⟶ 48:

}

}

</nowiki> -->

=== [[linguaggio Java|Java]] ===

<source lang="Java">

<nowiki>

private static void scambio(Object a[], int ind1, int ind2 ) {

Object tmp = a[ind1];

a[ind1] = a[ind2];

a[ind2] = tmp;

}

public static void selectionSort(Object a[]) {

for (int i=0; i < a.length-1; i++) {

int posMin = i;

for (int j = i+1; j < a.length; j++) {

if (((Comparable)a[j]).compareTo(a[posMin])<0) posMin = j;

}

scambio(a,i,posMin);

}

}

</nowikisource>

=== [[Pascal (linguaggio)|Pascal]] ===

<source lang="Pascal">

<nowiki>

program SelectionSort(input,output);

const dim=20;

procedure SelectionSort(var a: array[1..dim] of integer);

var

n,i,j,pos,min,aus:integer;

begin

// Creazione vettore di n elementi (con 1<=n<=dim)

pos:=0;

for i:=1 to n-1 do begin

minpos:= a[i];

for j:=(i+1) to n do begin

if a[j]< mina[pos] then begin

min:= a[j];

pos:= j;

end;

end;

aus:= a[i];

a[i]:= mina[pos];

a[pos]:= aus;

end;

end;

// Stampa del vettore

</source>

readln;

end.

===[[PHP|PHP]]===

</nowiki>

<source lang="PHP">

===[[PHP|PHP]]===

<nowiki>

function selection_sort(&$a) {

for($i = 1; $i < count($a)-1; $i++) {

$min_index = $j;

for($j = $i + 1; $j < count($a); $j++)

if ($arraya[$ij] >< $a[$ji]) {

$transfermin_index = $a[$j];

$array[$j]transfer = $a[$imin_index];

$array[$imin_index] = $transfera[$i];

$array[$i] = $transfer;

}

}

}

</nowikisource>

== Analisi delle prestazioni ==

Il ciclo interno è un semplice test per confrontare l'elemento corrente con il minimo elemento trovato fino a quel momento (più il codice per incrementare l'indice dell'elemento corrente e per verificare che esso non ecceda i limiti dell'array). Lo spostamento degli elementi è fuori dal ciclo interno: ogni scambio pone un elemento nella sua posizione finale quindi il numero di scambi è pari a <math> N-1</math> (dato che l'ultimo elemento non deve essere scambiato). Il tempo di calcolo è determinato dal numero di confronti.