|
Ordinamenti ingenui |
   |
|
|
Scambiare i valori contenuti nell'array v alle posizioni a e b static void SCAMBIA(double[] v, int a, int b)
{
double temp=v[a];
v[a]=v[b];
v[b]=temp;
}
Ordinare un array di due elementi if(v[0] > v[1]) SCAMBIA(v, 0, 1); oppure... if(v[0] > v[1])
{
double temp=v[0];
v[0]=v[1];
v[1]=temp;
}
Ordinare un sottoarray di due elementi if(v[i] > v[i+1]) SCAMBIA(v, i, i+1); Una passataUna passata su tutte le N-1 coppie, all'interno di un array, provoca lo spostamento "in alto" della "bolla" più grande for(int i=0; i < v.length-1; i++)
if(v[i] > v[i+1])
SCAMBIA(v, i, i+1);
Cioè l'elemento più grande si trova in ultima posizione alla fine della passata. Bubble SortN passate, sulle N-1 coppie, ordinano sicuramente l'array static void BUBBLESORT(double[] v)
{
int n=v.length;
for(int i=0; i < n; i++)
for(int j=0; j < n-1; j++)
if(v[j] > v[j+1])
SCAMBIA(v, j, j+1);
}
In realtà sono necessarie al massimo N-1 passate su N-i coppie static void BUBBLESORT(double[] v)
{
int n=v.length;
for(int i=0; i < n-1; i++)
for(int j=0; j < n-i-1; j++)
if(v[j] > v[j+1])
SCAMBIA(v, j, j+1);
}
Selection SortSi può individuare il minimo e scambiarlo con il valore alla posizione 0: in questo modo l'elemento alla posizione 0 occuperà definitivamente il posto che gli spetta... int posMin=0;
for(j=1; j < n; j++)
if(v[j] < v[posMin])
posMin=j;
SCAMBIA(v, 0, posMin);
Si ripete l'operazione con il sottovettore con indice da 1 a N-1, da 2 a N-1, ... e ogni elemento andrà al posto che gli spetta. static void SELESORT(double[] v)
{
int n=v.length;
for(int i=0; i < n-1; i++)
{
int posMin=i;
for(j=i+1; j < n; j++)
if(v[j] < v[posMin])
posMin=j;
SCAMBIA(v, i, posMin);
}
} |
|