El algoritmo de ordenación por inserción es una técnica sencilla pero efectiva para organizar elementos dentro de un arreglo. Su objetivo es lograr que cada elemento sea menor o igual que el siguiente, garantizando así que la lista quede ordenada de menor a mayor.
El proceso comienza recorriendo cada elemento del arreglo. Para cada uno, comprobamos si está en la posición correcta respecto a los elementos que tiene a la izquierda. Si el elemento que está a la izquierda es mayor que el actual, significa que están desordenados y debemos intercambiarlos. Este intercambio se repite hasta que el elemento quede en una posición donde el que está a su izquierda sea menor o igual, o hasta que llegue a la primera posición del arreglo, donde no puede moverse más.
Imaginemos un vector desordenado, por ejemplo: [6, 4, 2, 1, 3, 5]. Empezamos con el primer elemento, el 6. Como no tiene ningún elemento a su izquierda, ya está ordenado. Luego pasamos al 4, que sí tiene un elemento mayor a su izquierda (6), por lo que intercambiamos ambos. Ahora el 4 está en la primera posición y no puede moverse más, así que avanzamos al siguiente elemento.
Este proceso se repite con cada elemento: el 2 se mueve hacia la izquierda intercambiándose con 6 y 4, el 1 se mueve aún más hacia la izquierda, pasando por 6, 4 y 2, y así sucesivamente. A medida que avanzamos, los elementos a la izquierda de la posición actual están ordenados, mientras que los que quedan a la derecha aún no lo están.
Para implementar este algoritmo en código, utilizamos un bucle que recorre el arreglo de izquierda a derecha, representando la flecha que avanza. Para cada posición, guardamos el valor del elemento que queremos ordenar en una variable temporal. Luego, mediante un bucle while, comprobamos si podemos mover ese elemento hacia la izquierda, es decir, si no está en la primera posición y si el elemento a su izquierda es mayor. Si ambas condiciones se cumplen, intercambiamos los elementos y reducimos la posición para seguir comprobando hacia la izquierda.
Un ejemplo básico en código Java podría ser:
for (int i = 1; i < n; i++) {
int pos = i;
while (pos > 0 && array[pos - 1] > array[pos]) {
int temp = array[pos];
array[pos] = array[pos - 1];
array[pos - 1] = temp;
pos--;
}
}
Sin embargo, este enfoque no es muy eficiente porque realiza muchos intercambios, lo que puede ralentizar el proceso. Para optimizarlo, en lugar de intercambiar elementos repetidamente, podemos guardar el valor que queremos insertar y desplazar hacia la derecha los elementos mayores, dejando espacio para insertar el valor guardado en la posición correcta. De esta forma, el valor se escribe solo una vez, reduciendo el número de operaciones.
La versión optimizada en código Java sería algo así:
for (int i = 1; i < n; i++) {
int valor = array[i];
int pos = i;
while (pos > 0 && array[pos - 1] > valor) {
array[pos] = array[pos - 1];
pos--;
}
array[pos] = valor;
}
Con esta mejora, el algoritmo sigue funcionando igual, pero es más rápido porque minimiza la cantidad de escrituras en el arreglo. Aunque el algoritmo de ordenación por inserción tiene una complejidad cuadrática en el peor caso, es muy útil para arreglos pequeños o casi ordenados, y su lógica es fácil de entender e implementar.