Cuando tenemos una lista de datos que son ordinales (por ejemplo números, o letras del abcdario) es probable que querramos darle un orden. Esto es bueno, para poder utilizar otros algoritmos, por ejemplo búsqueda. Básicamente lo que hace este algoritmo es:

  • Cómo entrada tenemos un arreglo u otra estructura compatible con elementos ordenables, que vamos a llamar v.
  • Vamos a recorrer i veces este arreglo, donde i es el tamaño de nuestro arreglo. Esto quiere decir que se recorrerá el arreglo una vez por cada elemento que contenga. 
  • Tendremos además un contador j, que iniciará en i-1, y recorrerá todo el arreglo a la izquierda del elemento i. 
  • Se guardará el elemento i en una variable temporal.
  • Para posteriormente recorrer todo el arreglo de j a 0. Si algún elemento es major que la variable temporal se intercambiarán. De lo contrario se recorrerá el arreglo.
  • Esto significa que se recorre el arreglo hasta que se encuentre el mejor lugar para insertar el elemento temporal. 
  • Este procedimiento se repite hasta que se haya concluido con todos los elementos de el arreglo. En este momento también el arreglo también estará ordenado. 

By Simpsons contributor [CC BY-SA 3.0  (https://creativecommons.org/licenses/by-sa/3.0)], from Wikimedia Commons

 

Para poder tener una mejor idea, dejaremos abajo el código que implementa el algoritmo en C.

 void insert_sort(int v[], int size)
{
int i, j, temp;
for(i=0; i<size; i++)
{
temp=v[i];
j=i-1;
while(j>=0 && v[j] >temp)
{
v[j+1] = v[j];
j--;
}

v[j+1] = temp;
}
}

Cómo podemos ver, el procedimiento es bastante sencillo. Sin embargo tiene un alto costo computacional. En el mejor de los casos, podría llegar a ser O(n), sin embargo, en el peor de los casos es O(n2). Dado que no siempre se encuentra en el peor de los casos, este procedimiento tiene una ligera ventaja sobre un ordenamiento con fuerza bruta. 

Para el que guste usar el código directo en su compilador, puede hacerlo fácilmente con el código completo que les dejamos a continuación. 


/*
* Descripción: Programa que genera listas
* aleatorias para después
* ordenarlas con el algoritmo de
* inserción.
*
* Lenguaje: ANSI C
*
* Bajo licencia GPL 3
*/

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define V_SIZE 10

int cont;

// Herramientas
void gen_rand(int v[], int size);
void print_vect(int v[], int size);
void swap(int v[], int o, int d);

//Algoritmos
void insert_sort(int v[], int size);

int main(int argc, char *argv[])
{
int v[V_SIZE];

printf("############ Ordenando por Inserción ##########\n");
gen_rand(v, V_SIZE);
printf("No. Aleatorios: ");
print_vect(v, V_SIZE);
printf("Números ordenados: ");
insert_sort(v, V_SIZE);
print_vect(v, V_SIZE);
return 0;
}
void gen_rand(int v[], int size)
{
int i;

cont = cont + 1;
srand(time(NULL)*cont);
for(i=0; i<size; i++)
v[i]=rand()%100;
}


void print_vect(int v[], int size)
{
int i;
printf("[ ");
for(i=0; i<size; i++)
printf("%d ", v[i]);
printf("]\n");
}


void insert_sort(int v[], int size)
{
int i, j, temp;
for(i=0; i<size; i++)
{
temp=v[i];
j=i-1;
while(j>=0 && v[j] >temp)
{
v[j+1] = v[j];
j--;
}

v[j+1] = temp;
}
}

Share This