3 Ordenamiento por Inserción

1. Descripción.

Este algoritmo también es bastante sencillo. ¿Has jugado cartas?. ¿Cómo las vas ordenando cuando las recibes? Yo lo hago de esta manera: tomo la primera y la coloco en mi mano. Luego tomo la segunda y la comparo con la que tengo: si es mayor, la pongo a la derecha, y si es menor a la izquierda (también me fijo en el color, pero omitiré esa parte para concentrarme en la idea principal). Después tomo la tercera y la comparo con las que tengo en la mano, desplazándola hasta que quede en su posición final. Continúo haciendo esto, insertando cada carta en la posición que le corresponde, hasta que las tengo todas en orden. ¿Lo haces así tu también? Bueno, pues si es así entonces comprenderás fácilmente este algoritmo, porque es el mismo concepto.

Para simular esto en un programa necesitamos tener en cuenta algo: no podemos desplazar los elementos así como así o se perderá un elemento. Lo que hacemos es guardar una copia del elemento actual (que sería como la carta que tomamos) y desplazar todos los elementos mayores hacia la derecha. Luego copiamos el elemento guardado en la posición del último elemento que se desplazó.

2. Pseudocódigo en C.

Tabla de variables
Nombre Tipo Uso
lista Cualquiera Lista a ordenar
TAM Constante Entera Tamaño de la lista
i Entero Contador
j Entero Contador
temp El mismo que los elementos de la lista Para realizar los intercambios
 
    1. for (i=1; i<TAM; i++)
    2.      temp = lista[i];
    3.      j = i - 1;
    4.      while ( (lista[j] > temp) && (j >= 0) )
    5.           lista[j+1] = lista[j];
    6.           j--;
    7.      lista[j+1] = temp;
 

Nota: Observa que en cada iteración del ciclo externo los elementos 0 a i forman una lista ordenada.

3. Un ejemplo

¿Te acuerdas de nuestra famosa lista?

4 - 3 - 5 - 2 - 1

temp toma el valor del segundo elemento, 3. La primera carta es el 4. Ahora comparamos: 3 es menor que 4. Luego desplazamos el 4 una posición a la derecha y después copiamos el 3 en su lugar.

4 - 4 - 5 - 2 - 1

3 - 4 - 5 - 2 - 1

El siguiente elemento es 5. Comparamos con 4. Es mayor que 4, así que no ocurren intercambios.

Continuamos con el 2. Es menor que cinco: desplazamos el 5 una posición a la derecha:

3 - 4 - 5 - 5 - 1

Comparamos con 4: es menor, así que desplazamos el 4 una posición a la derecha:

3 - 4 - 4 - 5 - 1

Comparamos con 3. Desplazamos el 3 una posición a la derecha:

3 - 3 - 4 - 5 - 1

Finalmente copiamos el 2 en su posición final:

2 - 3 - 4 - 5 - 1

El último elemento a ordenar es el 1. Cinco es menor que 1, así que lo desplazamos una posición a la derecha:

2 - 3 - 4 - 5 - 5

Continuando con el procedimiento la lista va quedando así:

2 - 3 - 4 - 4 - 5

2 - 3 - 3 - 4 - 5

2 - 2 - 3 - 4 - 5

1 - 2 - 3 - 4 - 5

Espero que te haya quedado claro.

4. Análisis del algoritmo.

  • Estabilidad: Este algoritmo nunca intercambia registros con claves iguales. Por lo tanto es estable.
  • Requerimientos de Memoria: Una variable adicional para realizar los intercambios.
  • Tiempo de Ejecución: Para una lista de n elementos el ciclo externo se ejecuta n-1 veces. El ciclo interno se ejecuta como máximo una vez en la primera iteración, 2 veces en la segunda, 3 veces en la tercera, etc. Esto produce una complejidad O(n2).

Ventajas:

  • Fácil implementación.
  • Requerimientos mínimos de memoria.

Desventajas:

  • Lento.
  • Realiza numerosas comparaciones.

Este también es un algoritmo lento, pero puede ser de utilidad para listas que están ordenadas o semiordenadas, porque en ese caso realiza muy pocos desplazamientos.

Comentarios de los usuarios (1)

Guillermo Escalona
2012-11-04 07:54:58

Una duda, del siguiente codigo que ordena candenas de manera ascendente o descendente por el metodo de insercion como puedo determinar el numero de comparaciones que se hacen? Comente algo en el while que dice comparacion++ porque ahi es mi duda, espero me la puedan resolver

#include "stdafx.h"
#include <iostream>
#include <time.h>
#include <conio.h>
#define LARGOCADENA 20
#define NUMCADENAS 30000
using namespace std;
int _tmain(int argc, _TCHAR* argv[])
{
	int i,j,opc,a,intercambios=0,comparacion=0;
	char cadena[LARGOCADENA];
	clock_t generacion,orden;
	//declaracion estructura
	struct cadenita
	{
		char cadenota[LARGOCADENA];
	};
	//Arreglo de estructuras
	struct cadenita cadenon[NUMCADENAS];
	srand(time(NULL));
	do
	{
		system("cls");
		cout<<"Como desea ordenar los numeros:"<<endl;
		cout<<"1. Menor a Mayor"<<endl;
		cout<<"2. Mayor a Menor"<<endl;
		cin>>opc;
		if(opc!=1&&opc!=2)
		{
			cout<<"Seleccione una opcion valida"<<endl;
			getch();
		}
	}
	while(opc!=1&&opc!=2);
	if(opc==1)
		a=1;
	else
		a=-1;
	/*creacion de numeros desordenados*/
	generacion=clock();
	for(j=0;j<NUMCADENAS;j++)
	{
		for(i=0; i<LARGOCADENA-1; i++)
		{
			cadena[i] = '0'+ ( rand() % ('0' - '9') );
		}
		cadena[i] = '\0';
		strcpy(cadenon[j].cadenota,cadena);
		cout<<cadenon[j].cadenota<<endl;
	}
	printf( "Numero de segundos transcurridos desde el comienzo del programa: %f s\n", (clock()-generacion)/(double)CLOCKS_PER_SEC );
	/*ordenarlos*/
	orden=clock();
	for(i=0;i<NUMCADENAS-1;i++)
	{
		j=i;
		while(a==(strcmp(cadenon[j].cadenota,cadenon[j+1].cadenota))/*,comparacion++*/)
		{
			strcpy(cadena,cadenon[j].cadenota);
			strcpy(cadenon[j].cadenota,cadenon[j+1].cadenota);
			strcpy(cadenon[j+1].cadenota,cadena);
			intercambios++;
			if(j!=0)
				j--;
		}
	}
	/*Mostrar datos ordenados*/
	for(j=0;j<NUMCADENAS;j++)
	{
		cout<<cadenon[j].cadenota<<endl;
	}
	cout<<"El numero de intercambios fue "<<intercambios<<endl;
	printf( "Numero de segundos transcurridos durante el ordenamiento: %f s\n", (clock()-(generacion+orden))/(double)CLOCKS_PER_SEC );
	getch();
	return 0;
}