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.

 Grafica de comportamiento del algoritmo de inserción directa

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 (&reg_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],&reg_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.

Algoritmo de ordenación. Inserción directa

Be Sociable, Share!