Ordenamiento por inserción

Ordenamiento por inserción

Ordenamiento por inserción

El ordenamiento por inserción es una manera muy natural de ordenar para un ser humano, y puede usarse fácilmente para ordenar un mazo de cartas numeradas en forma arbitraria.

La idea de este algoritmo de ordenación consiste en ir insertando un elemento de la lista ó un arreglo en la parte ordenada de la misma, asumiendo que el primer elemento es la parte ordenada, el algoritmo ira comparando un elemento de la parte desordenada de la lista con los elementos de la parte ordenada, insertando el elemento en la posición correcta dentro de la parte ordenada, y así sucesivamente hasta obtener la lista ordenada.

Representación animada del ordenación por inserción :

Representación animada del ordenación por inserción

  1. PROCEDIMIENTO Insertion_sort ( Vector a[1:n])
  2.     PARA i VARIANDO DE 2 HASTA n HACER
  3.         INSERTAR a[i] EN SU LUGAR EN a[1:i-1];
  4. FIN PROCEDIMIENTO;
  1. let Insertion_sort Vector =
  2.     for i = 1 to 19 do     
  3.         let actual = Vector.(i) and j = ref (i - 1) in
  4.             (* Desplazamiento de los elementos de la matriz *)
  5.             while (!j>=0) && (Vector.(!j)>actual) do            
  6.                 Vector.(!j + 1) <-  Vector.(!j);    
  7.                 j := !j - 1;
  8.             done;
  9.             (* insertar el elemento en su lugar *)
  10.             Vector.(!j + 1) <- actual;
  11.     done;
  12. Vector;;
  1. type tab = array[1..20] of integer;
  2. procedure Insertion_sort(var Vector : tab);
  3. var i, j, actual : integer;
  4. begin
  5.     for i:=2 to 20 do
  6.     begin
  7.         actual := Vector[i]; j := i - 1;  
  8.         {Desplazamiento de los elementos de la matriz }
  9.         while (j > 0) and (Vector[j] > actual) do
  10.         begin
  11.             Vector[j + 1] :=  Vector[j];              
  12.             j := j - 1;
  13.         end;
  14.         {insertar el elemento en su lugar }
  15.         Vector[j + 1] := actual;
  16.     end;
  17. end
  1. def Insertion_sort(Vector):
  2.     for i in range(1,len(Vector)):
  3.         actual = Vector[i]
  4.         j = i
  5.         #Desplazamiento de los elementos de la matriz }
  6.         while j>0 and Vector[j-1]>actual:
  7.             Vector[j]=Vector[j-1]
  8.             j = j-1
  9.         #insertar el elemento en su lugar
  10.         Vector[j]=actual
  1. void Insertion_sort(int* t)
  2. {
  3.     int i, j;
  4.     int actual;
  5.  
  6.     for (i = 1; i < 20; i++) {
  7.         actual = t[i];
  8.         for (j = i; j > 0 && t[j - 1] > actual; j--) {
  9.             t[j] = t[j - 1];
  10.         }
  11.         t[j] = actual;
  12.     }
  13. }

Use este algoritmo para resolver el pequeño conjunto de la página anterior :



 



Los siguientes gráficos muestran el aumento en el número de transacciones en relación con el número de elementos a ser ordenados.

Rendimiento del algoritmo

En el caso óptimo, con los datos ya ordenados, el algoritmo sólo effectura n comparaciones. Por lo tanto la complejidad en el caso óptimo es en Θ(n).

Rendimiento en el caso óptimo Número de operaciones Número de términos Θ(n)

En el caso desfavorable, con los datos ordenados a la inversa, se necesita realizar (n-1) + (n-2) + (n-3) .. + 1 comparaciones e intercambios, o (n2-n) / 2. Por lo tanto la complejidad es en Θ(n2).

Rendimiento en el caso desfavorable Número de operaciones Número de términos Θ(n2)

En el caso medio, la complejidad de este algoritmo es también en Θ(n2)

Rendimiento en el caso medio Número de operaciones Número de términos Θ(n2)