Introducción al algoritmo de ordenación por inserción
El ordenamiento por inserción es una técnica que funciona utilizando una sublista ordenada y agregando continuamente un valor desde la lista sin ordenar hasta que se ordena toda la lista.
El algoritmo comienza con el primer elemento de la lista como sublista ordenada. Luego compara el siguiente número con el primero. Si es mayor, se inserta en el primer índice. De lo contrario, se deja en su índice.
Luego, el tercer valor se compara con los otros dos y luego se inserta en el índice correcto. Este proceso continúa hasta que se ordena toda la lista.
Una mirada más cercana al tipo de inserción
Es posible que la descripción anterior no tenga sentido para usted. Un ejemplo debería ayudarlo a comprender mucho mejor.
Suponga que tiene una lista: [39, 6, 2, 51, 30, 42, 7].
El algoritmo identifica 39 como el primer valor de la sublista ordenada. Luego, la evaluación pasa a la segunda posición.
A continuación, se compara 6 con 39. Dado que 6 es menor que 39, se inserta 6 en la primera posición y 39 en la segunda. El nuevo orden de la lista después del primer paso es ahora:
[6, 39, 2, 51, 30, 42, 7]
La evaluación ahora pasa a la tercera posición. 2 se compara con los dos últimos números y luego se inserta en la posición correcta. El nuevo orden de la lista después del segundo paso es ahora:
[2, 6, 39, 51, 30, 42, 7]
Para el tercer paso, el orden de la lista es:
[2, 6, 39, 51, 30, 42, 7]
El proceso se repite hasta que se ordena toda la lista.
Vea el diagrama a continuación que resume estas operaciones:
Análisis de algoritmos
La complejidad de tiempo de la ordenación por inserción es O (n 2 ), al igual que la ordenación por burbujas . El número de comparaciones en el peor de los casos es la suma de todos los números enteros de 1 a (n-1), lo que da una suma cuadrática.
Implementación de código
El código de Python y Java a continuación muestra cómo puede implementar el método de ordenación por inserción.
Pitón:
def insertionSort(mylist):
for step in range(1, len(mylist)):
current_element = mylist[step]
position = step
while position > 0 and mylist[position - 1] > current_element:
mylist[position] = mylist[position - 1]
position = position - 1
mylist[position] = current_elementJava:
void insertionSort(int[] myarray) {
int n = myarray.length;
for (int x = 1; x < n; x++) {
int key = myarray[x];
int y = x-1;
while ( (y > -1) && ( myarray [y] > key ) ) {
myarray [y+1] = myarray [y];
y--;
}
myarray[y+1] = key;
}
}Mejor codificación con pseudocódigo
Los ejemplos de código anteriores se proporcionaron sin ningún pseudocódigo al que pueda hacer referencia para escribir este algoritmo en otros idiomas. A la mayoría de los programadores (incluido el autor) les gusta ejecutar sus teclados después de que les digan "susurros" sobre cómo funciona un programa.
Desafortunadamente, este enfoque es propenso a errores a medida que la lógica del programa se vuelve más complicada. ¿Cómo le gustaría subir de nivel su juego de programación aprendiendo a usar pseudocódigo?