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

Pseudocódigo
Caml
Pascal
Python
C
Modelo gráfico
Diagrama

PROCEDIMIENTO Insertion_sort ( Vector a[1:n])
PARA i VARIANDO DE 2 HASTA n HACER
INSERTAR a[i] EN SU LUGAR EN a[1:i-1];
FIN PROCEDIMIENTO;

let Insertion_sort Vector =
for i = 1 to 19 do
let actual = Vector.(i) and j = ref (i - 1) in
(* Desplazamiento de los elementos de la matriz *)
while (!j>=0) && (Vector.(!j)>actual) do
Vector.(!j + 1) <- Vector.(!j);
j := !j - 1;
done;
(* insertar el elemento en su lugar *)
Vector.(!j + 1) <- actual;
done;
Vector;;

type tab = array[1..20] of integer;
procedure Insertion_sort(var Vector : tab);
var i, j, actual : integer;
begin
for i:=2 to 20 do
begin
actual := Vector[i]; j := i - 1;
{Desplazamiento de los elementos de la matriz }
while (j > 0) and (Vector[j] > actual) do
begin
Vector[j + 1] := Vector[j];
j := j - 1;
end;
{insertar el elemento en su lugar }
Vector[j + 1] := actual;
end;
end

def Insertion_sort(Vector):
for i in range(1,len(Vector)):
actual = Vector[i]
j = i
#Desplazamiento de los elementos de la matriz }
while j>0 and Vector[j-1]>actual:
Vector[j]=Vector[j-1]
j = j-1
#insertar el elemento en su lugar
Vector[j]=actual

void Insertion_sort(int* t)
{
int i, j;
int actual;
for (i = 1; i < 20; i++) {
actual = t[i];
for (j = i; j > 0 && t[j - 1] > actual; j--) {
t[j] = t[j - 1];
}
t[j] = actual;
}
}

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

Comparaciones :
Movimientos :

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

Rendimiento en el caso óptimo
Rendimiento en el caso desfavorable
Rendimiento en el caso medio

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).

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 Θ(n²).

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