Ordenamiento por Inserción

Ordenamiento por Inserción
Ordenamiento por Inserción: Supóngase que se desea ordenar los siguientes claves del arreglo (A) utilizando el método de inserción directael cual consiste en insertar unelemento del arreglo en la parte izquierda del mismo que ya se encuentra ordenada. Este proceso se repite desde el segundo hasta el n-esimo elemento.

Insercion (A,N), Algoritmo

Insercion(A,N)El algoritmo ordena los elementos del arreglo utlizando el método de inserción directa A es un arreglo de N elementos 
donde I, aux y k son variables de tipo entero
1.- Repetir con I desde 2 hasta N Haceraux<- A[I] y k<- I-1
a. Repetir mientras(aux < [k]) y (k > 1) , Hacer A[k+1]<- A[k] y k<-- k-1
b. {fin del ciclo del paso 1.1}
c. Si a[k]<=aux Entonces: Hacer A[k+1]<-aux
Si no Hacer A[k+1]<- A[k],A[k]<-A[k]
d. { fin del condicional del paso 1.3}
2. {fin del condicional del paso1}

Implementación
A continuación se muestra el ordenamiento por inserción en distintos lenguajes de programación:
C
voidInsercion(int numbers[], int array_size) {
int i, a, index;
for (i=1; i < array_size; i++) {
index = numbers[i];
a = i-1;
while (a >= 0 && numbers[a] > index) {
numbers[a + 1] =numbers[a];
a--;
}
numbers[a+1] = index;
}
}
Python
def Insercion(numeros): #numeros es una lista
tama = len(numeros) #tamaño de la lista
i=0
for i in range(tama):
indice =numeros[i]
a = i-1
while (a >= 0 and numeros[a] > indice):
numeros[a+1] = numeros[a]
a = a-1
numeros[a+1] = indice
print numeros #imprime la lista ordenada
PHP
functionInsercion($arr){
$count = count($arr);
for($i=1; $i<$count; $i++){
$tmp = $arr[$i];
for ($j=$i-1; $j>=0 && $arr[$j] > $tmp; $j--)
$arr[$j+1] = $arr[$j];
$arr[$j] = $tmp;
}
return$arr;
}

Prueba de escritorio

Si A= 15, 67, 08, 16, 44, 27, 12, 35
1ª pasada 08, 67, 15, 16, 44, 27, 12, 35
2ª pasada 08, 15, 67, 16, 44, 27, 12, 35
3ª pasada 08, 15, 16, 67, 44, 27, 12, 35
4ª...