El método de ordenación por inserción directa consiste en recorrer todo el array comenzando desde el segundo elemento hasta el final. Para cada elemento, se trata de colocarlo en el lugar correcto entre todos los elementos anteriores a él o sea entre los elementos a su izquierda en el array.
Dada una posición actual p, el algoritmo se basa en que los elementos A[0], A[1], ..., A[p-1] ya están ordenados.
public static void insercionDirecta(int A[]){
int p, j;
int aux;
for (p = 1; p < A.length; p++){ // desde el segundo elemento hasta
aux = A[p]; // el final, guardamos el elemento y
j = p - 1; // empezamos a comprobar con el anterior
while ((j >= 0) && (aux < A[j])){ // mientras queden posiciones y el
// valor de aux sea menor que los
A[j + 1] = A[j]; // de la izquierda, se desplaza a
j--; // la derecha
}
A[j + 1] = aux; // colocamos aux en su sitio
}
} asi seria un ejemplo
La idea central de este algoritmo consiste en insertar un elemento del arreglo en la parte izquierda del mismo, que ya se encuentra ordenada. Este proceso se repite desde el segundo hasta el n-esimo elemento.
Ejemplo:
Se desean ordenarse las siguientes clave del arreglo A: 15, 67, 08, 16, 44, 27, 12, 35
Primera pasadaA[2] < A[1] 67 < 15 No hay intercambio
A: 15, 67, 08, 16, 44, 27, 12, 35
Segunda pasadaA[3] < A[2] 08 < 67 Si hay intercambio
A[2] < A[1] 08 < 15 Si hay
A: 15, 08, 67, 16, 44, 27, 12, 35
Tercera pasada
A[4] < A[3] 08 < 15 Si hay intercambio
A[3] < A[2] 08 < 15 Si hay intercambio
A= 08, 15, 67, 16, 44, 27, 12, 35
Hasta la septima pasada el arreglo queda ordenado: 08, 12, 15, 16, 27, 35, 44, 67
El número máximo de comparaciones y movimientos se produce cuando los elementos del arreglo están en orden inverso Cmax = 1+2+3+............+(n-1) = n*(n-1)/2 Cmax= (n2-n)/2
El número de comparaciones promedio que es cuando los elementos aparecen en el arreglo en forma aleatoria, puede ser calculado mediante la suma de las comparaciones mínimas y máximas divididas entre 2.
Cmed = [(n-1) + (n2-n)/2]/2
Al hacer la operación, nos queda:
Cmed = (n2+n-2)/4
R
especto al número de movimientos Knuth obtiene los siguiente:
Mmin = 0 Mmed = (n2-n)/4 Mmax = (n2-n)/2
El tiempo necesario para ejecutar el algoritmo es proporcionar a n2, O(n2). A pesar de ser un método ineficiente y recomendable solo cuando n es pequeña, el método de inserción directa se comporta mejor que el método de intercambio directo analizado anteriormente.
El número de comparaciones promedio que es cuando los elementos aparecen en el arreglo en forma aleatoria, puede ser calculado mediante la suma de las comparaciones mínimas y máximas divididas entre 2.
Cmed = [(n-1) + (n2-n)/2]/2
Al hacer la operación, nos queda:
Cmed = (n2+n-2)/4
R
especto al número de movimientos Knuth obtiene los siguiente:
Mmin = 0 Mmed = (n2-n)/4 Mmax = (n2-n)/2
El tiempo necesario para ejecutar el algoritmo es proporcionar a n2, O(n2). A pesar de ser un método ineficiente y recomendable solo cuando n es pequeña, el método de inserción directa se comporta mejor que el método de intercambio directo analizado anteriormente.
BIBLIOGRAFIA: http://www.angelfire.com/wy2/est_info/insercion.html
NOTA: se encuentra un ejercicio en este link
Mas informacion
Comentarios
Publicar un comentario