En este artículo se describe el algoritmo de ordenamiento por inserción y su aplicación en varios lenguajes.

El algoritmo de ordenamiento por inserción es un algoritmo de fácil aplicación que permite el ordenamiento de una lista.

Su funcionamiento consiste en el recorrido por la lista seleccionando en cada iteración un valor como clave y compararlo con el resto insertándolo en el lugar correspondiente.

Ordenamiento por inserción

Comenzamos con una lista de elementos no ordenados

Se selecciona el segundo valor como clave y se lo compara con los valores ubicados a su izquierda. Si el valor es menor entonces se inserta en el lugar correspondiente.

Se selecciona el siguiente número como clave y se repite el proceso para todos los valores anteriores. En el siguiente caso la clave 4 se compara primero con 5 y luego con 2. Al ser menor que el primer caso comparado y mayor que el segundo se lo inserta entre ambos números.

Se selecciona la siguiente clave. Se sigue comparando con cada número a su izquierda hasta encontrar uno que sea menor o llegar al principio de la lista.

Finalmente se selecciona la última clave.

Al finalizar el algoritmo tenemos como resultado la lista ordenada.

Código en C

#include<stdio.h>
#define N 5
void mostrarLista(int*);
int main(int argc, char** argv){
	int arreglo[N]={5,2,4,1,3};
	int i,clave,j;
   //Recorrer el arreglo
	for (i = 1; i < N; i++){	   
		clave = *(arreglo+i);
		j = i-1;
		//Comparar el valor selecionado con todos los valores anteriores
		while (j >= 0 && *(arreglo+j) > clave){
			//Insertar el valor donde corresponda
			*(arreglo+j+1) = *(arreglo+j);
			j = j-1;
		}
		*(arreglo+j+1) = clave;
		mostrarLista(arreglo);
	}    
	mostrarLista(arreglo);  
	return 0;
}
//Función para mostrar estado de la lista
void mostrarLista(int *lista){
	int i;
	for (i=0; i< N; i++){
		printf("%d ",*(lista+i));
	}
	printf("\n");;
   
}

Código en PHP

<?php
$arreglo = [5,2,4,1,3];
 //Recorrer el arreglo
   for ($i = 1; $i < count($arreglo); $i++)
   {	   
       $clave = $arreglo[$i];
       $j = $i-1;
       //Comparar el valor seleccionado con todos los valores anteriores
       while ($j >= 0 && $arreglo[$j] > $clave)
       {
		   //Insertar el valor donde corresponda
		   $arreglo[$j+1] = $arreglo[$j];
           $j = $j-1;
       }
       $arreglo[$j+1] = $clave;
       mostrarLista($arreglo, count($arreglo));
   }    
   mostrarLista($arreglo, count($arreglo));    
//Función para mostrar estado de la lista
function mostrarLista($lista, $lon)
{
   for ($i=0; $i< $lon; $i++)
   {
       echo $lista[$i]." ";
   }
   echo "<br />";   
}

Código en Python

#Función para mostrar estado de la lista
def mostrarLista(lista, lon):
	listaordenada=""
	for i in range(0,lon):
		listaordenada+=str(lista[i])+" "
	print(listaordenada)   
	
arreglo = [5,2,4,1,3];
#Recorrer el arreglo
for i in range(1,len(arreglo)):
	clave = arreglo[i]
	j = i-1
	#Comparar el valor seleccionado con todos los valores anteriores
	while (j>=0 and arreglo[j] > clave):
		#Insertar el valor donde corresponda
		arreglo[j+1] = arreglo[j]
		j = j-1
	arreglo[j+1] = clave
	mostrarLista(arreglo, len(arreglo))
mostrarLista(arreglo, len(arreglo))    

Espero que les sea de utilidad!