Insertion Sort
Se trata de un algoritmo de ordenamiento bastante simple, de hecho es el algoritmo que usamos los humanos para ordenar.
Entrada: la sequencia
Salida: la permutación
Ejemplo:
Entrada: 8 2 4 9 3 6
Salida : 2 3 4 6 8 9
En la siguiente figura se muestra el costo de ejecución de cada una de las líneas que componen el algoritmo y el número de veces que éstas se ejecutan.
Análisis del Tiempo de ejecución
Para el mejor de los casos (el algoritmo ya está ordenado de forma ascendente)
Cabe mencionar que el encabezado de los ciclos se ejecutan una vez más que el contenido de los mismos. Cuando el arreglo ya se encuentra ordenado el ciclo while de la linea 5 se ejecuta una vez en cada repetición del ciclo exterior. Por lo que tj = 1. Las líneas 6 y 7 nunca se ejecutan.
T(n) = c1n + c2(n – 1) + c4(n – 1) + c5(n – 1) + c8(n – 1)
= (c1 + c2 + c4 + c5 + c8)n – (c2+ c4 + c5 + c8).
Vemos que tiene la forma an + b, por lo tanto es una función lineal de n.
using namespace std;
void print_array(int a[],int n){
for (int i=0; i<n; i++)
printf ("%d",a[i]),
printf (i < n-1 ? ",":"\n");
}
void insertion_sort(int a[], int n){
int i,j,key;
for (j = 1; j < n; j++){
key = a[j];
i = j - 1;
while (i >= 0 and a[i] > key){
a[i+1] = a[i];
i= i -1;
}
a[i+1]=key;
}
}
int main(){
int n,i;
int array[100];
scanf ("%d\n",&n);
for (i=0; i<n; i++)
scanf ("%d",&array[i]);
printf ("original:"); print_array(array,n);
insertion_sort(array,n);
printf ("ordenado:"); print_array(array,n);
return 0;
}
