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 directa el cual consiste en insertar un elemento 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 Hacer aux<- 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

void Insercion(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

function Insercion($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ª pasada 08, 15, 16, 44, 67, 27, 12, 35
5ª pasada 08, 15, 16, 44, 27, 67, 12, 35
6ª pasada 08, 15, 16, 44, 27, 12, 67, 35
7ª pasada 08, 15, 16, 44, 27, 12, 35, 67

Análisis de la eficiencia

En general afirmar que si el arreglo se encuentra ordenado se efectúan como máximo n-1 comparaciones y o movimientos entre elementos Cmin = n-1.

El número máximo de comparaciones y movimientos se produce cuando los elementos del arreglo están en orden inverso
Cmax = 1+2+3+............+(n-1) = n*(n-1)/2
Cmax= (n2-n)/2

El número de comparaciones promedio que es cuando los elementos aparecen en el arreglo en forma aleatoria, puede ser calculado mediante la suma de las comparaciones mínimas y máximas divididas entre 2.
Cmed = [(n-1) + (n2-n)/2]/2
Al hacer la operación, nos queda:
Cmed = (n2+n-2)/4
Respecto al número de movimientos Knuth obtiene los siguiente:
Mmin = 0
Mmed = (n2-n)/4
Mmax = (n2-n)/2

Tiempo de ejecución

El tiempo necesario para ejecutar el algoritmo es proporcionar a n2, O(n2).
A pesar de ser un método ineficiente y recomendable solo cuando n es pequeña, el método de inserción directa se comporta mejor que el método de intercambio directo.

Fuentes

• http://latecladeescape.com/con-nombre-propio/ordenacion-por-insercion-directa-insertionsort.html
  
• http://www.mitecnologico.com/Main/OrdenamientoPorInsercion
  
• http://snippets-tricks.org/ordenacion-insercion/