Insertion sort
void insertion_sort (int a[ ],int N)
{
int i, j, v;
a[0] = INT_MIN;
for (i=2; i<=N; i++)
{
v=a[i]; j=i;
while ( a[j-1]>v)
{ a[j]=a[j-1]; j--; }
a[j]=v;
}
}
Algoritmo Insertion sort senza sentinella
void ordina(int a[], const int n)
{
int i, j, v, t;
for (i=n;i>1;i--)
if (a[i-1]>a[i]){
t = a[i-1]; a[i-1]= a[i]; a[i]=t; }
// minimo nella prima posizione
for (i=2; i<=n; i++){
v=a[i]; j=i;
while ( a[j-1]>v)
{ a[j]=a[j-1]; j--; }
a[j]=v;
}
}
Insertion sort
0
1
2
3
Int
Min
3
2
1
2
3
3
1
i
j-a[j]=v
4
5
5
j
i++
j=i
SI
NO
a[j-1]>v
a[j]=a[j-1];
v=a[i];
4
2
1
v
il ciclo continua …
Presentazione realizzata dall’ing. G. Marti