Algoritmo De Inserción En SL Guía Detallada Y Código Paso A Paso

Aug 2, 2025 by Viktoria Ivanova 65 views

¡Hola, gente! Hoy vamos a sumergirnos en el fascinante mundo de los algoritmos de ordenamiento, y vamos a hacerlo con un clásico: el algoritmo de inserción. Este algoritmo es súper útil para ordenar listas pequeñas y medianas, y es genial para entender cómo funcionan los algoritmos de ordenamiento en general. Para hacerlo aún más interesante, vamos a explorar cómo implementar este algoritmo en el lenguaje SL. ¡Así que prepárense para aprender y codificar!

¿Qué es el Algoritmo de Inserción?

El algoritmo de inserción, también conocido como insertion sort, es un método de ordenamiento que funciona de manera similar a cómo ordenaríamos una baraja de cartas en nuestras manos. Imaginen que tienen una mano de cartas desordenadas. Toman una carta a la vez y la insertan en la posición correcta dentro de las cartas que ya tienen ordenadas. Este proceso se repite hasta que todas las cartas estén en el orden correcto.

La belleza de este algoritmo radica en su simplicidad. Es fácil de entender e implementar, lo que lo convierte en una excelente opción para principiantes en el mundo de la programación y los algoritmos. Sin embargo, es importante tener en cuenta que su eficiencia disminuye a medida que el tamaño de la lista aumenta, lo que lo hace menos adecuado para conjuntos de datos muy grandes. Pero para listas pequeñas y medianas, ¡funciona de maravilla!

Paso a Paso del Algoritmo de Inserción

Para que quede aún más claro, vamos a desglosar el algoritmo de inserción en pasos sencillos:

Inicio: Consideramos el primer elemento de la lista como si ya estuviera ordenado. Técnicamente, una lista de un solo elemento está ordenada, ¿verdad?
Iteración: Recorremos la lista desde el segundo elemento hasta el último. Para cada elemento:
- Lo comparamos con los elementos que están a su izquierda (es decir, los elementos que ya hemos considerado como ordenados).
- Si el elemento es menor que alguno de los elementos a su izquierda, lo insertamos en la posición correcta, desplazando los elementos mayores hacia la derecha.
Repetición: Repetimos el paso 2 hasta que hayamos recorrido toda la lista.
Final: ¡La lista está ordenada!

Para visualizar esto, piensen en una lista como [5, 2, 4, 6, 1, 3]. Vamos a ver cómo el algoritmo de inserción la ordenaría paso a paso:

[5, 2, 4, 6, 1, 3] – Inicialmente, [5] se considera ordenado.
[2, 5, 4, 6, 1, 3] – Insertamos 2 antes de 5.
[2, 4, 5, 6, 1, 3] – Insertamos 4 entre 2 y 5.
[2, 4, 5, 6, 1, 3] – 6 ya está en su posición correcta.
[1, 2, 4, 5, 6, 3] – Insertamos 1 al principio.
[1, 2, 3, 4, 5, 6] – Insertamos 3 en su posición correcta.

¡Y ahí lo tienen! La lista está ordenada. ¿Ven cómo funciona? Es como organizar cartas en la mano, moviendo cada carta a su lugar correcto.

Ventajas y Desventajas del Algoritmo de Inserción

Como todo algoritmo, el de inserción tiene sus pros y sus contras. Vamos a echarles un vistazo:

Ventajas:

Simple de implementar: Como mencionamos antes, es un algoritmo fácil de entender y codificar.
Eficiente para listas pequeñas: Funciona muy bien cuando la lista no es muy grande.
Ordenamiento en línea: Puede ordenar la lista a medida que recibe los elementos, sin necesidad de tener todos los elementos al principio.
Estable: Mantiene el orden relativo de los elementos con el mismo valor. Esto significa que si tienen dos elementos iguales, su orden original se conserva después de la ordenación.
Adaptativo: Es eficiente para listas que ya están parcialmente ordenadas. Si la lista está casi ordenada, el algoritmo de inserción funciona muy rápido.

Desventajas:

Ineficiente para listas grandes: Su rendimiento disminuye significativamente a medida que el tamaño de la lista aumenta. En el peor de los casos, tiene una complejidad de tiempo de O(n^2), lo que significa que el tiempo de ejecución crece cuadráticamente con el número de elementos.
No es adecuado para grandes volúmenes de datos: Para grandes conjuntos de datos, otros algoritmos como Merge Sort o Quick Sort son mucho más eficientes.

En resumen, el algoritmo de inserción es una excelente opción para listas pequeñas y medianas, especialmente si ya están parcialmente ordenadas. Pero para listas grandes, es mejor buscar alternativas más eficientes.

Implementación del Algoritmo de Inserción en SL

Ahora viene la parte emocionante: ¡vamos a codificar el algoritmo de inserción en SL! Para aquellos que no estén familiarizados, SL es un lenguaje de programación didáctico, ideal para aprender los fundamentos de la programación. Es simple, claro y perfecto para entender cómo funcionan los algoritmos.

Vamos a tomar el código SL que mencionaste y lo vamos a desglosar paso a paso, explicando cada parte para que quede súper claro. Aquí está el código (con algunas modificaciones y explicaciones):

programa OrdenarArreglo
constantes
    N = 12 // Número total de elementos
variables
    arreglo : arreglo[1..N] de entero // Nuestro arreglo de enteros
    i, j, clave : entero // Variables para iterar y guardar el valor a insertar

procedimiento LeerArreglo()
variables
    k : entero
inicio
    para k := 1 hasta N hacer
        escribir "Ingrese el elemento ", k, ": "
        leer arreglo[k]
    finpara
finprocedimiento

procedimiento ImprimirArreglo()
variables
    k : entero
inicio
    escribir "Arreglo ordenado: "
    para k := 1 hasta N hacer
        escribir arreglo[k], " "
    finpara
    escribir "\n"
finprocedimiento

procedimiento OrdenarPorInsercion()
inicio
    para i := 2 hasta N hacer // Empezamos desde el segundo elemento
        clave := arreglo[i] // Guardamos el valor actual
        j := i - 1 // Índice del elemento anterior

        mientras j >= 1 y arreglo[j] > clave hacer // Movemos elementos mayores a la derecha
            arreglo[j + 1] := arreglo[j]
            j := j - 1
        finmientras

        arreglo[j + 1] := clave // Insertamos el valor en su posición correcta
    finpara
finprocedimiento




inicio
    LeerArreglo() // Leemos los elementos del arreglo
    OrdenarPorInsercion() // Ordenamos el arreglo
    ImprimirArreglo() // Imprimimos el arreglo ordenado
finprograma

Desglose del Código SL

Vamos a analizar cada parte del código para entender cómo funciona el algoritmo de inserción en SL:

Declaración de Constantes y Variables
```
constantes
    N = 12 // Número total de elementos
variables
    arreglo : arreglo[1..N] de entero // Nuestro arreglo de enteros
    i, j, clave : entero // Variables para iterar y guardar el valor a insertar
```
Aquí declaramos la constante N, que define el tamaño del arreglo (12 en este caso). Luego, declaramos las variables:
- arreglo: Es el arreglo de enteros que vamos a ordenar. En SL, los arreglos se indexan desde 1, así que va desde 1 hasta N.
- i y j: Son variables que utilizaremos para iterar a través del arreglo.
- clave: Esta variable es crucial. La usaremos para guardar el valor del elemento que estamos intentando insertar en la posición correcta.
Procedimiento LeerArreglo()
```
procedimiento LeerArreglo()
variables
    k : entero
inicio
    para k := 1 hasta N hacer
        escribir "Ingrese el elemento ", k, ": "
        leer arreglo[k]
    finpara
finprocedimiento
```
Este procedimiento se encarga de leer los elementos del arreglo desde la entrada del usuario. Usamos un bucle para para iterar a través de cada posición del arreglo y pedimos al usuario que ingrese un valor para cada elemento.
Procedimiento ImprimirArreglo()
```
procedimiento ImprimirArreglo()
variables
    k : entero
inicio
    escribir "Arreglo ordenado: "
    para k := 1 hasta N hacer
        escribir arreglo[k], " "
    finpara
    escribir "\n"
finprocedimiento
```
Este procedimiento es simple: imprime los elementos del arreglo en la consola. También usamos un bucle para para iterar a través del arreglo y mostrar cada elemento, seguido de un espacio.
Procedimiento OrdenarPorInsercion()
```
procedimiento OrdenarPorInsercion()
inicio
    para i := 2 hasta N hacer // Empezamos desde el segundo elemento
        clave := arreglo[i] // Guardamos el valor actual
        j := i - 1 // Índice del elemento anterior

        mientras j >= 1 y arreglo[j] > clave hacer // Movemos elementos mayores a la derecha
            arreglo[j + 1] := arreglo[j]
            j := j - 1
        finmientras

        arreglo[j + 1] := clave // Insertamos el valor en su posición correcta
    finpara
finprocedimiento
```
¡Aquí está el corazón del algoritmo! Vamos a desglosarlo línea por línea:
- para i := 2 hasta N hacer: Este bucle para itera a través del arreglo desde el segundo elemento (índice 2) hasta el último (índice N). ¿Por qué empezamos desde el segundo elemento? Porque consideramos el primer elemento como si ya estuviera ordenado (una lista de un solo elemento está ordenada, ¿recuerdan?).
- clave := arreglo[i]: Guardamos el valor del elemento actual (arreglo[i]) en la variable clave. Este es el valor que vamos a insertar en la posición correcta.
- j := i - 1: Inicializamos la variable j con el índice del elemento anterior al actual. Esta variable nos ayudará a comparar el valor de clave con los elementos que están a su izquierda.
- mientras j >= 1 y arreglo[j] > clave hacer: Este bucle mientras es crucial. Aquí es donde movemos los elementos mayores que clave hacia la derecha para hacer espacio para la inserción. La condición j >= 1 asegura que no nos salgamos del arreglo, y arreglo[j] > clave verifica si el elemento actual (arreglo[j]) es mayor que clave. Si ambas condiciones son verdaderas, significa que necesitamos mover arreglo[j] una posición a la derecha.
  - arreglo[j + 1] := arreglo[j]: Movemos el elemento arreglo[j] a la posición j + 1.
  - j := j - 1: Decrementamos j para comparar clave con el siguiente elemento a la izquierda.
- arreglo[j + 1] := clave: Después de que el bucle mientras termina, hemos encontrado la posición correcta para clave. Insertamos clave en la posición j + 1.
Programa Principal (inicio ... finprograma)
```
inicio
    LeerArreglo() // Leemos los elementos del arreglo
    OrdenarPorInsercion() // Ordenamos el arreglo
    ImprimirArreglo() // Imprimimos el arreglo ordenado
finprograma
```
El programa principal es sencillo: llama a los procedimientos LeerArreglo(), OrdenarPorInsercion() y ImprimirArreglo() en ese orden. Primero, leemos los elementos del arreglo. Luego, ordenamos el arreglo utilizando el algoritmo de inserción. Finalmente, imprimimos el arreglo ordenado.

Ejemplo de Ejecución

Si ejecutamos este código y ingresamos los siguientes valores para el arreglo:

Ingrese el elemento 1: 5
Ingrese el elemento 2: 2
Ingrese el elemento 3: 4
Ingrese el elemento 4: 6
Ingrese el elemento 5: 1
Ingrese el elemento 6: 3
Ingrese el elemento 7: 9
Ingrese el elemento 8: 7
Ingrese el elemento 9: 8
Ingrese el elemento 10: 10
Ingrese el elemento 11: 11
Ingrese el elemento 12: 12

La salida será:

Arreglo ordenado: 1 2 3 4 5 6 7 8 9 10 11 12

¡Funciona! El arreglo se ha ordenado correctamente de menor a mayor.

Optimización del Algoritmo de Inserción

Aunque el algoritmo de inserción es simple y efectivo para listas pequeñas, podemos optimizarlo un poco para mejorar su rendimiento. Una de las optimizaciones más comunes es utilizar la búsqueda binaria para encontrar la posición correcta para insertar el elemento. Esto reduce el número de comparaciones necesarias, especialmente en listas más grandes.

Búsqueda Binaria en el Algoritmo de Inserción

En la versión básica del algoritmo de inserción, comparamos el elemento actual (clave) con cada elemento a su izquierda hasta encontrar la posición correcta. Esto puede ser ineficiente si la parte ordenada de la lista es grande. La búsqueda binaria nos permite encontrar la posición correcta de manera más rápida.

La búsqueda binaria funciona dividiendo repetidamente la parte ordenada de la lista por la mitad hasta encontrar la posición correcta. Aquí están los pasos:

Definir límites: Inicializamos dos variables, izquierda y derecha, que representan los límites de la parte ordenada de la lista.
Calcular el punto medio: Calculamos el punto medio (medio) entre izquierda y derecha.
Comparar: Comparamos clave con el elemento en la posición medio.
- Si clave es igual al elemento en medio, hemos encontrado la posición.
- Si clave es menor que el elemento en medio, buscamos en la mitad izquierda de la lista.
- Si clave es mayor que el elemento en medio, buscamos en la mitad derecha de la lista.
Repetir: Repetimos los pasos 2 y 3 hasta que encontremos la posición correcta o los límites se crucen.

Implementación en SL (con Búsqueda Binaria)

Aquí está el código SL con la optimización de búsqueda binaria:

programa OrdenarArregloBinario
constantes
    N = 12 // Número total de elementos
variables
    arreglo : arreglo[1..N] de entero // Nuestro arreglo de enteros
    i, j, clave, izquierda, derecha, medio : entero // Variables para iterar y guardar el valor a insertar

procedimiento LeerArreglo()
variables
    k : entero
inicio
    para k := 1 hasta N hacer
        escribir "Ingrese el elemento ", k, ": "
        leer arreglo[k]
    finpara
finprocedimiento

procedimiento ImprimirArreglo()
variables
    k : entero
inicio
    escribir "Arreglo ordenado: "
    para k := 1 hasta N hacer
        escribir arreglo[k], " "
    finpara
    escribir "\n"
finprocedimiento

funcion BusquedaBinaria(izquierda : entero, derecha : entero, clave : entero) : entero
variables
    medio : entero
inicio
    mientras izquierda <= derecha hacer
        medio := (izquierda + derecha) div 2
        si arreglo[medio] = clave entonces
            retornar medio
        finsi
        si clave < arreglo[medio] entonces
            derecha := medio - 1
        sino
            izquierda := medio + 1
        finsi
    finmientras
    retornar izquierda // Retornamos la posición donde debería insertarse
finfuncion

procedimiento OrdenarPorInsercionBinaria()
inicio
    para i := 2 hasta N hacer
        clave := arreglo[i]
        izquierda := 1
        derecha := i - 1

        j := BusquedaBinaria(izquierda, derecha, clave) // Encontramos la posición con búsqueda binaria

        para j := i - 1 downto j hacer // Movemos los elementos mayores a la derecha
            arreglo[j + 1] := arreglo[j]
        finpara

        arreglo[j + 1] := clave // Insertamos el valor en su posición correcta
    finpara
finprocedimiento

inicio
    LeerArreglo()
    OrdenarPorInsercionBinaria()
    ImprimirArreglo()
finprograma

Cambios Clave en el Código

Función BusquedaBinaria(): Esta función implementa la búsqueda binaria. Recibe los límites izquierda y derecha de la parte ordenada de la lista y el valor clave que queremos buscar. Retorna la posición donde clave debería insertarse.
Procedimiento OrdenarPorInsercionBinaria(): Este procedimiento utiliza la función BusquedaBinaria() para encontrar la posición correcta para insertar cada elemento. En lugar de comparar clave con cada elemento a su izquierda, llamamos a BusquedaBinaria() para encontrar la posición de manera más eficiente.

¿Mejora el Rendimiento?

La optimización de búsqueda binaria reduce el número de comparaciones necesarias para encontrar la posición correcta, lo que puede mejorar el rendimiento del algoritmo de inserción, especialmente para listas más grandes. Sin embargo, la búsqueda binaria en sí misma tiene un costo, y la mejora real depende del tamaño de la lista y de cómo esté ordenada inicialmente.

Conclusión

¡Felicidades, chicos! Hemos explorado el algoritmo de inserción en detalle, desde su funcionamiento básico hasta su implementación en el lenguaje SL y una optimización con búsqueda binaria. Espero que esta guía les haya sido útil para entender este algoritmo clásico y cómo aplicarlo en sus propios proyectos.

El algoritmo de inserción es una herramienta valiosa en el arsenal de cualquier programador. Aunque no es el algoritmo más eficiente para listas muy grandes, su simplicidad y eficiencia para listas pequeñas lo convierten en una excelente opción en muchas situaciones. ¡Así que sigan practicando y explorando el mundo de los algoritmos!

Si tienen alguna pregunta o comentario, ¡no duden en dejarlo abajo! ¡Hasta la próxima!