Técnicas de clasificación y búsqueda. Algoritmo de inserción directa.
Publicado por lcflores en Julio 2nd 2007
El algoritmo de inserción directa tiene un funcionamiento muy sencillo. La filosofía es recorrer en orden el conjunto de elementos de uno en uno desde el primero al último. Para cada elemento se busca el punto de inserción entre los elementos ya recorridos de forma que el elemento a insertar quede ordenado, para buscar la posición se recorren los elementos de uno en uno desde el último elemento ordenado.
A priori, se puede pensar que podríamos mejorar fácilmente el algoritmo incluyendo una búsqueda binaria para saber cual es la posición donde debe insertarse el elemento. No obstante, está mejora no sería una buena práctica ya que este algoritmo se utiliza y tiene muy buen rendimiento cuando los datos están prácticamente ya ordenados, en estos casos además el número de intercambio de registros durante la ordenación es mínimo. En la próxima gráfica puede apreciarse fácilmente.
Donde:
- La serie azul: muestra el comportamiento con registros desordenados.
- La serie naranja: muestra el comportamiento con registros ordenados.
- La serie amarilla: muestra el comportamiento con registros ordenados de forma inversa.
Vamos a ver un ejemplo de implementación del algoritmo de inserción directa en C:
/*-----------------------------------------------------------------------------------*/
// Funciones y definiciones auxiliares
typedef struct {
long int campo[NCAMPOS]; // campos tipo int
} REGISTRO_s;
typedef struct {
long int N; // tamaño del array
long int c; // campo clave en ordenacion
REGISTRO_s *reg; // registros del array
} ARRAY_s;
void CopiarReg(REGISTRO_s *reg1, REGISTRO_s *reg2) {
long int i;
for (i=0;i<num_c;i++){ // copia campos tipo 1
reg1->campo[i] = reg2->campo[i];
}
}
/*-----------------------------------------------------------------------------------*/
// Algoritmo de insercion_directa
void InsercionDirecta(ARRAY_s *A) {
long int i, j;
REGISTRO_s reg_x;
for (i=1;i< A->N; i++){
CopiarReg (®_x, &A->reg[i]); // Selecciona última carta
j = i-1; // busca punto de inserción
while ( (j>=0) && (reg_x.campo[A->c] < A->reg[j].campo[A->c]) ){
CopiarReg (&A->reg[j+1], &A->reg[j]);
j--; // alternando comparaciones y movimientos
}
CopiarReg (&A->reg[j+1],®_x); // Inserta la carta
}
}
/*-----------------------------------------------------------------------------------*/
Debajo de estas líneas podéis ver de una forma más sencilla el funcionamiento del algoritmo. Cada una de las gráficas representa el estado de los elementos en un instante de la ejecución de forma que puede apreciarse perfectamente como evoluciona la ordenación de los elementos durante la ejecución del algoritmo.
Publicado en Algoritmos, Programación | 2 Comentarios »