El algoritmo de Inserción fue mencionado por John William Mauchly en 1.946. Entre los algoritmos de ordenación simple es la mejor opción, realiza un menor número de comparaciones respecto del de burbuja y del de selección. Compara los elementos del vector según lo recorre, desplazando los existentes si el actual es mayor o menor (según la implementación), de tal forma que los elementos ordenados quedan en uno de los extremos del vector.
| Rendimiento – Complejidad | |||
| Mejor caso Ω |
Peor caso O |
Media Θ |
Espacio |
| (n) | (n2) | (n2) | O(1) |
Es estable, adaptable, in situ y en linea. Quizás su mayor fortaleza radica en evitar comparaciones innecesarias cuando los datos están parcialmente ordenados. Es muy eficiente para conjuntos pequeños de datos, aunque pertenezca al grupo de algoritmos de clasificación cuadrática O(n2), que son los que peor rendimiento ofrecen (Burbuja, Selección, etc). Si la secuencia de entrada está ordenada o parcialmente ordenada solo verifica el orden y no realiza ningún movimiento o pocos, en este caso la complejidad se acerca O(n). Se usa en muchas ocasiones como apoyo en algoritmos más complejos (Timsort).
Inserción Binaria.
La Inserción Binaria es idéntica al algoritmo de inserción salvo que utiliza la búsqueda binaria para encontrar el lugar adecuado para la inserción. Esta versión tiene un menor número de comparaciones O(n log n), pero la complejidad promedio es O (n2 ), esto no es una mejora importante. La inserción en sus dos versiones sólo son convenientes en vectores muy pequeños.
Ejemplos.
public static int[] Ordenainsercion(int[] Vector) {
{
int longitudV = Vector.length;
for (int i = 1; i < longitudV; ++i) {
int actual = Vector[i];
int j = i - 1;
while (j >= 0 && Vector[j] > actual) {
Vector[j + 1] = Vector[j];
j = j - 1;
}
Vector[j + 1] = actual;
}
}
return Vector;
}
public static int[] OrdenaInsercionBinaria (int[] Vector) {
int n = Vector.length;
int mayor = 0;
int menor = 0;
int medio = 0;
int v =0;
for (int i = 1; i < n; i++) {
v = Vector[i];
menor = 0;
mayor = i;
while (menor < mayor) {
medio = menor + (mayor - menor) / 2;
if (v < Vector[medio])
mayor = medio;
else
menor = medio + 1;
}
for (int j = i; j > menor; --j)
Vector[j] = Vector[j - 1];
Vector[menor] = v;
}
return Vector;
}
Rendimiento.
Estadística individual realizada con el mismo equipo y condiciones del resumen de estadísticas de ordenación. Destacar los datos completamente planos al tratar vectores ya clasificados de forma ascendente, para el resto y a partir de más de 1.000 elementos, recordando, son algoritmos desaconsejables.
