Laboratorio 1 de Algoritmos

Juan Eduardo Benítez Pájaro

Rubén Santiago Blandón Ardila

000515362

000521227

Análisis y diseño de algoritmos

Juan Carlos Nariño Morantes

1 de Agosto

1
 2. ÍNDICE
Laboratorio 1 de Algoritmos........................................................................................... 1
2. ÍNDICE ..................................................................................................................... 2
1. INTRODUCCIÓN .................................................................................................... 2
2. PLANTEAMIENTO DEL PROBLEMA .......................................................................... 2
Ejercicio 1 ordenamiento por inserción .................................................................... 4
Segundo ejercicio búsqueda binaria ...................................................................... 11
4 EJERCICIO COMPLEJIDAD DE UNA FUNCIÓN ...................................................... 17
2. Planteamiento del problema ................................................................................ 17
5 EJERCICIO: ENCONTRAR LOS PARES DE NÚMEROS EN UN AREGLO CUYA SUMA ES
UN NÚMERO DADO .............................................................................................. 20
2. Planteamiento del problema ................................................................................ 20
Referencias ......................................................................................................... 22

1. INTRODUCCIÓN
En el ámbito de la informática, los algoritmos de ordenamiento y búsqueda son fundamentales para
la manipulación eficiente de datos. El ordenamiento por inserción es un método clásico que permite
organizar elementos en una lista de manera incremental, lo que lo hace especialmente útil para
conjuntos de datos pequeños o casi ordenados. Por otro lado, la búsqueda binaria es una técnica
eficaz para localizar un elemento en una lista ordenada, reduciendo significativamente el tiempo
de búsqueda en comparación con métodos más simples.
Este laboratorio tiene como objetivo que los estudiantes adquieran una comprensión profunda de
ambos algoritmos, implementando el ordenamiento por inserción y la búsqueda binaria, y
analizando su complejidad temporal. A través de un enfoque tanto analítico como empírico, se
aprenderán a aplicar dichos algoritmos, y se evaluarán su rendimiento en diferentes condiciones,
lo que les permitirá apreciar su relevancia en la resolución de problemas computacionales reales.

2. PLANTEAMIENTO DEL PROBLEMA

La eficiencia en el manejo de datos es esencial en el hábito de la programación. A medida que los
volúmenes de información crecen, se vuelve crucial entender y aplicar algoritmos, los cuales
optimicen el rendimiento de las operaciones y funciones de los programas.

2
Por eso es importante el aplicar aplicar y comprender dos algoritmos fundamentales: el algoritmo
de ordenamiento por inserción y el algoritmo de búsqueda binaria. Por ende se realizara un
análisis tanto analítico como empírico de la complejidad temporal de estos algoritmos a partir de
los ejercicios proporcionados.

3
Ejercicio 1 ordenamiento por inserción

4
5
Planteamiento del Problema:
Contexto En el ámbito de la programación y la informática, el ordenamiento es una tarea
fundamental. Consiste en organizar un conjunto de elementos (como números, palabras o
registros) en un orden específico, ya sea ascendente o descendente. Uno de los algoritmos más
sencillos y ampliamente utilizado para ordenar elementos es el algoritmo de ordenamiento por
inserción.

Problema a Resolver
El objetivo principal es implementar un programa que ordene una lista de elementos utilizando el
algoritmo de ordenamiento por inserción. En particular, se nos pide:

Entrada de Datos:

El programa debe permitir al usuario ingresar una lista de elementos (por ejemplo, números
enteros, nombres o cualquier otro tipo de dato comparable).
La cantidad de elementos en la lista puede variar según la preferencia del usuario.

Ordenamiento por Inserción:

Una vez que el usuario ha ingresado la lista, el programa debe aplicar el algoritmo de
ordenamiento por inserción para organizar los elementos en orden ascendente (de menor a
mayor).

El algoritmo de ordenamiento por inserción funciona de la siguiente manera:

Comienza con una lista desordenada.

En cada paso, toma un elemento de la lista desordenada y lo inserta en la posición correcta dentro
de la lista ordenada.

6
Repite este proceso hasta que todos los elementos estén en su posición correcta.

Salida de Resultados:
Una vez ordenada la lista, el programa debe mostrar los elementos en el nuevo orden.

Puede hacerlo mediante una ventana emergente (como JOptionPane en Java) o simplemente
imprimiendo los resultados en la consola.

Ejemplo

Supongamos que el usuario desea ordenar una lista de nombres:

El usuario ingresa los siguientes nombres: “Ana”, “Carlos”, “Eva”, “David”, “Beto”.

El programa aplica el algoritmo de ordenamiento por inserción y obtiene la lista ordenada:

“Ana”, “Beto”, “Carlos”, “David”, “Eva”.

El programa muestra la lista ordenada al usuario.

Consideraciones Adicionales

El programa debe ser eficiente y manejar correctamente cualquier cantidad de elementos.

Se debe validar que los datos ingresados sean del tipo esperado (por ejemplo, números enteros o
cadenas de texto).

Hipótesis:
Hipótesis: El algoritmo de ordenamiento por inserción tiene una complejidad temporal de
O(n^2), donde “n” es la cantidad de elementos en la lista.
Justificación: Dado que el algoritmo compara y mueve elementos uno por uno, se espera que su
tiempo de ejecución sea cuadrático en función del tamaño de la entrada.

Hipótesis de Mejor Caso:

Hipótesis: El mejor caso para el algoritmo de ordenamiento por inserción ocurre cuando la lista
ya está ordenada.

Justificación: En este escenario, no se necesitarán movimientos adicionales, y el algoritmo solo

realizará comparaciones para confirmar que la lista está ordenada.
Hipótesis de Peor Caso:

7
Hipótesis: El peor caso para el algoritmo de ordenamiento por inserción ocurre cuando la lista
está ordenada en orden inverso (mayor a menor).
Justificación: En este caso, cada elemento debe ser comparado y movido hasta su posición
correcta, lo que resulta en un alto número de operaciones.

Hipótesis de Estabilidad:

Hipótesis: El algoritmo de ordenamiento por inserción es estable, es decir, mantiene el orden

relativo de elementos iguales.

Justificación: Dado que solo se intercambian elementos adyacentes, no se altera el orden de

elementos con el mismo valor.

Hipótesis de Espacio:

Hipótesis: El algoritmo de ordenamiento por inserción es in-place, es decir, no requiere memoria

adicional significativa más allá de la lista original.

Justificación: El algoritmo solo necesita espacio para almacenar variables temporales y no crea
estructuras de datos adicionales.

Detalle de la Implementación
Lenguaje de Programación

Java se usa mucho en el desarrollo de aplicaciones por su portabilidad, robustez y comunidad

activa.

Entorno de Desarrollo (NetBeans)

NetBeans IDE: NetBeans es un entorno de desarrollo integrado (IDE) gratuito y de código

abierto que proporciona herramientas avanzadas para escribir, depurar y ejecutar programas Java.
Puedes descargar NetBeans desde su sitio oficial: NetBeans Downloads.

Funcionamiento del Programa

El usuario ingresa la cantidad de elementos que desea ordenar.

Luego, ingresa los valores uno por uno mediante ventanas emergentes (JOptionPane).

El algoritmo de ordenamiento por inserción se aplica a los elementos ingresados.

Finalmente, se muestra el arreglo ordenado en otra ventana emergente.

8
Enfoque analítico
1. Descripción del Algoritmo:

El algoritmo de ordenamiento por inserción es un método simple y eficiente para organizar una
lista de elementos en un orden específico (generalmente ascendente o descendente). A
continuación, explicaré detalladamente cómo funciona:

Pasos del Algoritmo:

Comenzamos con una lista desordenada.

Tomamos un elemento de la lista desordenada y lo insertamos en la posición correcta dentro de la

lista ordenada.
Repetimos el paso anterior hasta que todos los elementos estén en su posición correcta.

Ejemplo: Supongamos que tenemos la siguiente lista de números: 5, 2, 9, 1, 5.

Comenzamos con una lista vacía (la lista ordenada).

Tomamos el primer elemento (5) y lo insertamos en la lista ordenada.

Luego, tomamos el siguiente elemento (2) y lo insertamos antes de 5.

Continuamos con los demás elementos siguiendo el mismo proceso.

2. Justificación Teórica: Razones para la Selección del Algoritmo

La elección del algoritmo de ordenamiento por inserción se basa en varias consideraciones:

Simplicidad: Es uno de los algoritmos más sencillos de entender e implementar.

Eficiencia en Pequeñas Listas: Funciona bien para listas pequeñas o casi ordenadas.

In-Place: No requiere memoria adicional significativa más allá de la lista original.

Estabilidad: Mantiene el orden relativo de elementos iguales.

3. Análisis de Complejidad

Complejidad Temporal:
Peor Caso: O(n^2) comparaciones y movimientos, donde “n” es la cantidad de elementos.
9
Mejor Caso (Lista ya Ordenada): O(n) comparaciones y ningún movimiento.

Promedio (Caso General): Aunque también es O(n^2), tiende a ser más rápido que otros
algoritmos cuadráticos debido a su estructura de comparaciones.

Complejidad Espacial:

Utiliza espacio adicional solo para variables temporales (O(1)).

Enfoque empírico, resultados experimentales

Comparación con las Hipótesis

Complejidad Temporal:

El tiempo de ejecución se ajusta a la complejidad teórica de O(n^2) en el peor caso.

Los resultados empíricos confirman esta hipótesis.

Mejor Caso (Lista ya Ordenada):

En el mejor caso, el algoritmo debería ser más rápido.

Sin embargo, debido a la naturaleza de los datos aleatorios, no observamos una mejora
significativa en el tiempo de ejecución.

10
Segundo ejercicio búsqueda binaria

Planteamiento del problema:

Contexto

En el ámbito de la programación y la informática, la búsqueda es una operación fundamental.

Consiste en encontrar un elemento específico dentro de una colección de datos. Uno de los
algoritmos más eficientes para buscar elementos en una lista ordenada es el algoritmo de
búsqueda binaria.

Problema a Resolver

Supongamos que tenemos una lista ordenada de elementos (por ejemplo, números enteros,
nombres o cualquier otro tipo de dato comparable). El objetivo es implementar un programa que
realice la búsqueda de un elemento específico en esta lista utilizando el algoritmo de búsqueda
binaria. En particular, se nos pide:

Entrada de Datos:

El usuario proporciona la lista ordenada (ya sea ingresando los elementos manualmente o
leyéndolos desde un archivo o base de datos).

También ingresa el elemento que desea buscar en la lista.

Búsqueda Binaria:
El programa aplica el algoritmo de búsqueda binaria para encontrar el elemento deseado.

El algoritmo funciona de la siguiente manera:

Compara el elemento buscado con el elemento central de la lista.

Si son iguales, se ha encontrado el elemento.

Si el elemento buscado es menor que el elemento central, se busca en la mitad inferior de la lista.

Si es mayor, se busca en la mitad superior.

Repite este proceso hasta encontrar el elemento o determinar que no está presente en la lista.
Salida de Resultados:

11
El programa muestra si el elemento buscado se encuentra en la lista y, en caso afirmativo, su
posición (índice).
Ejemplo

Supongamos que tenemos la siguiente lista ordenada de números: 1, 3, 5, 7, 9, 11, 13, 15.

El usuario ingresa el número 7.

El programa aplica la búsqueda binaria y encuentra que el número 7 está en la posición 3 (índice
2) de la lista.
Consideraciones Adicionales

El programa debe manejar correctamente cualquier cantidad de elementos en la lista.

Se debe validar que los datos ingresados sean del tipo esperado (por ejemplo, números enteros o
cadenas de texto).

Hipótesis
Hipótesis de Eficiencia:

Hipótesis: El algoritmo de búsqueda binaria tiene una complejidad temporal de O(log n), donde
“n” es la cantidad de elementos en la lista.

Justificación: Dado que el algoritmo divide la búsqueda a la mitad en cada paso, se espera que su
tiempo de ejecución sea logarítmico en función del tamaño de la entrada.

Hipótesis de Mejor Caso:

Hipótesis: El mejor caso para el algoritmo de búsqueda binaria ocurre cuando el elemento
buscado está en la posición central de la lista.

Justificación: En este escenario, se encuentra el elemento rápidamente sin necesidad de explorar

todas las mitades.

Hipótesis de Peor Caso:

Hipótesis: El peor caso para el algoritmo de búsqueda binaria ocurre cuando el elemento buscado
no está en la lista.
Justificación: En este caso, se deben explorar todas las mitades hasta determinar que el elemento
no está presente.

Hipótesis de Listas Grandes:

12
Hipótesis: La búsqueda binaria será más eficiente en listas grandes en comparación con la
búsqueda secuencial.
Justificación: La búsqueda binaria reduce significativamente el espacio de búsqueda en cada
paso.

Hipótesis de Estabilidad:

Hipótesis: El algoritmo de búsqueda binaria es estable y no altera el orden de los elementos en la

lista.

Justificación: Solo se compara y divide la lista sin realizar movimientos.

Detalles de la implementación
Se implemento el lenguaje de programación java y se uso el entorno de desarrollo NetBeans
Funcionamiento del Programa

El usuario ingresa el número que desea buscar.

El programa aplica la búsqueda binaria en la lista ordenada.

Muestra si el número está presente y, en caso afirmativo, su posición (índice).

1. Descripción del Algoritmo: Búsqueda Binaria

El algoritmo de búsqueda binaria, también conocido como búsqueda logarítmica, es un método

eficiente para encontrar un elemento específico en una lista ordenada. A continuación, explicaré
detalladamente cómo funciona:

Pasos del Algoritmo:

Comenzamos con una lista ordenada (por ejemplo, números enteros).

Calculamos el índice del elemento central de la lista.

Comparamos el elemento buscado con el elemento central:
Si son iguales, hemos encontrado el elemento.

13
Si el elemento buscado es menor que el elemento central, restringimos la búsqueda a la mitad
inferior de la lista.
Si es mayor, restringimos la búsqueda a la mitad superior.

Repetimos el proceso en la mitad seleccionada hasta encontrar el elemento o determinar que no

está presente.

2. Justificación Teórica: Razones para la Selección del Algoritmo

La elección del algoritmo de búsqueda binaria se basa en varias consideraciones:

Eficiencia: La búsqueda binaria reduce significativamente el espacio de búsqueda en cada paso,

lo que la hace más rápida que la búsqueda secuencial.

Complejidad Logarítmica: Su complejidad temporal es O(log n), lo que la hace adecuada para
listas grandes.

Orden de la Lista: Requiere que la lista esté ordenada, pero en muchos casos, esta restricción es
aceptable.

3. Análisis de Complejidad

Complejidad Temporal:
Peor Caso: O(log n) comparaciones, donde “n” es la cantidad de elementos en la lista.

Mejor Caso (Elemento en el Centro): O(1) comparaciones.

Promedio (Caso General): Aunque también es O(log n), tiende a ser más rápido que otros
algoritmos logarítmicos debido a su estructura de comparaciones.

Complejidad Espacial:
Utiliza espacio adicional solo para variables temporales (O(1)).

En resumen, la búsqueda binaria es una excelente opción para buscar elementos en listas
ordenadas, especialmente cuando se manejan grandes conjuntos de datos.

Enfoque analítico
Descripción del Algoritmo: Búsqueda Binaria

14
La búsqueda binaria es un algoritmo eficiente para encontrar un elemento específico en una lista
ordenada. A continuación, detallaré cómo funciona paso a paso:

Precondición:

La lista debe estar ordenada previamente (por ejemplo, en orden ascendente).

Inicialización:

Definimos dos índices: left (izquierda) y right (derecha).

left apunta al primer elemento de la lista, y right apunta al último elemento.

Búsqueda:

Calculamos el índice del elemento central: mid = (left + right) / 2.

Comparamos el elemento central con el elemento buscado:

Si son iguales, hemos encontrado el elemento.

Si el elemento buscado es menor que el elemento central, restringimos la búsqueda a la mitad

inferior (actualizamos right = mid - 1).

Si es mayor, restringimos la búsqueda a la mitad superior (actualizamos left = mid + 1).

Repetimos este proceso hasta que left sea mayor que right.
Resultado:

Si encontramos el elemento, devolvemos su posición (índice).

Si no, indicamos que el elemento no está en la lista.

Justificación Teórica: Razones para la Selección del Algoritmo

Eficiencia: La búsqueda binaria reduce significativamente el espacio de búsqueda en cada paso,
lo que la hace más rápida que la búsqueda secuencial.

Complejidad Logarítmica: Su complejidad temporal es O(log n), lo que la hace adecuada para
listas grandes.

Orden de la Lista: Aunque requiere que la lista esté ordenada, esta restricción es aceptable en
muchos casos.

Análisis de Complejidad

Complejidad Temporal:
Peor Caso: O(log n) comparaciones, donde “n” es la cantidad de elementos en la lista.
15
Mejor Caso (Elemento en el Centro): O(1) comparaciones.

Promedio (Caso General): Aunque también es O(log n), tiende a ser más rápido que otros
algoritmos logarítmicos debido a su estructura de comparaciones.

Complejidad Espacial:

Utiliza espacio adicional solo para variables temporales (O(1)).

3 analisis la complejidad del algoritmo

Inicialización:

La función toma dos argumentos:

v: Un arreglo de enteros.

tamaño: El tamaño del arreglo.

Bucle For:

La función recorre el arreglo v utilizando un bucle for.

En cada iteración, suma el elemento actual (v[i]) al resultado acumulado (result).

Resultado:

La función devuelve la suma total de todos los elementos en el arreglo.

Justificación Teórica

Eficiencia: La función recorre todos los elementos del arreglo una vez, por lo que su complejidad
temporal es O(n), donde “n” es el tamaño del arreglo.

Espacio: Utiliza espacio adicional solo para las variables i y result.

Análisis de Complejidad
16
Complejidad Temporal:

Peor Caso: O(n) comparaciones (recorre todo el arreglo).

Mejor Caso: O(1) comparaciones (si el arreglo está vacío).

Promedio: O(n) comparaciones.

Complejidad Espacial:

Utiliza espacio adicional para las variables temporales (O(1)).

4 EJERCICIO COMPLEJIDAD DE UNA FUNCIÓN

2. Planteamiento del problema

Contexto

En el ámbito de la programación y la informática, la búsqueda y la manipulación de datos son

operaciones fundamentales. En muchas aplicaciones, es necesario encontrar el valor mínimo en
una colección de datos, como una lista o un arreglo de números enteros. Este tipo de operación es
común en algoritmos de procesamiento de datos, análisis estadístico y optimización de recursos.

Problema a Resolver

Se nos pide implementar una función que encuentre el valor mínimo en un arreglo de números
enteros. Esta función debe ser eficiente y capaz de manejar arreglos de diferentes tamaños. La

17
tarea implica iterar a través de los elementos del arreglo y determinar cuál es el menor.
Entrada de Datos
Entrada de Datos

• Un arreglo de números enteros v[], que puede contener elementos positivos, negativos o
cero.
• Se asume que el arreglo tiene al menos un elemento.

HIPÓTESIS

Dado que la complejidad es O(n), podemos esperar que el tiempo de ejecución de la función
minimo crezca linealmente con el tamaño del arreglo v. Esto significa que, a medida que
aumentamos el número de elementos en v, el tiempo que toma encontrar el mínimo también
aumentará de manera proporcional.

Por lo tanto, si tenemos un arreglo más grande, podemos anticipar que el tiempo de ejecución
será mayor, pero siempre dentro de un comportamiento lineal.

ENFOQUE ANALÍTICO

Descripción del Algoritmo: Este algoritmo es eficiente y directo, permitiendo encontrar el valor
mínimo en un arreglo de enteros de manera rápida y con un uso mínimo de memoria. Es aplicable
en diversas situaciones donde se necesita analizar colecciones de datos numéricos.

Justificación Teórica: Para poder encontrar el valor mínimo en un arreglo de enteros, este se basa
en principios sólidos de la teoría de algoritmos, incluyendo la búsqueda lineal, la eficiencia en
términos de tiempo y espacio, y la garantía de correctitud. Estos factores hacen que el algoritmo
sea una solución robusta y eficiente para el problema planteado.

Análisis de la Complejidad: El análisis para encontrar el valor mínimo en un arreglo de números

enteros muestra que tiene una complejidad temporal de O(n) y una complejidad espacial de O(1).
Esto lo convierte en un algoritmo eficiente tanto en términos de tiempo como de uso de memoria,
lo que lo hace adecuado para una amplia gama de aplicaciones.

18
ENFOQUE EMPÍRICO, MUESTRA DE RESULTADOS

Comparación con la hipótesis:

Los resultados muestran un crecimiento lineal en el tiempo de ejecución a medida que

aumentamos el tamaño del arreglo, lo que coincide perfectamente con la hipótesis de que la
complejidad de la función mínimo es O(n). Esto indica que el algoritmo es eficiente y se

19
comporta de manera predecible con respecto al tamaño de la entrada. Si necesitas más
información o un análisis más profundo, házmelo saber.

5 EJERCICIO: ENCONTRAR LOS PARES DE NÚMEROS EN UN AREGLO CUYA

SUMA ES UN NÚMERO DADO

2. Planteamiento del problema

Contexto

20
En el desarrollo de aplicaciones que manejan datos numéricos, es común necesitar identificar
combinaciones de números que cumplan ciertas condiciones. Un caso típico es encontrar pares de
números que sumen un valor específico. Esta funcionalidad puede ser útil en diferentes areas
tales como la estadística, finanzas y análisis de datos, donde es necesario realizar cálculos
basados en conjuntos de números.

Problema a Resolver

El problema a desarrollar es una función que, dado un arreglo de números enteros y un número
objetivo, encuentre todos los pares únicos de números dentro del arreglo cuya suma sea igual al
número objetivo. Esta función debe ser eficiente y capaz de manejar arreglos de diferentes
tamaños.

Entrada de Datos

Arreglo: Un arreglo de números enteros. Por ejemplo: [1, 2, 3, 4, 5].

Número Objetivo: Un número entero que representa la suma que se desea alcanzar. Por ejemplo:
6.

Salida Esperada
La función debe devolver una lista de tuplas, donde cada tupla contiene dos números del arreglo
que suman el número objetivo. Por ejemplo, para la entrada mencionada, la salida esperada sería:
[(1, 5), (2, 4)].

HIPÓTESIS

Se plantea que, dado un conjunto de números enteros y un número objetivo, es posible identificar
eficientemente todos los pares únicos de elementos cuya suma sea igual al objetivo, lo que
sugiere que existen métodos algorítmicos efectivos para resolver problemas de combinaciones
aritméticas en diversas aplicaciones.

21
ENFOQUE ANALÍTICO

Descripción del Algoritmo: Este algoritmo busca identificar todos los pares únicos de números en
un arreglo de enteros cuya suma sea igual a un número objetivo. Utiliza una combinación de
estructuras de datos y técnicas de búsqueda para lograrlo de manera eficiente, permitiendo un
análisis efectivo de colecciones de datos numéricos.

Justificación Teórica El algoritmo se basa en principios fundamentales de la teoría de algoritmos,

como la búsqueda eficiente y la utilización de estructuras de datos adecuadas (como conjuntos o
diccionarios). Esto asegura que el algoritmo no solo sea correcto, sino que también minimice el
tiempo de ejecución al evitar comparaciones redundantes. La capacidad de manejar arreglos con
elementos duplicados y negativos refuerza su aplicabilidad en diversas situaciones.

Análisis de la Complejidad El análisis del algoritmo muestra que tiene una complejidad temporal
de O(n) en el caso del enfoque de hash, ya que cada elemento se procesa una sola vez. La
complejidad espacial es también O(n), debido al almacenamiento de los elementos en una
estructura de datos auxiliar. Esto lo convierte en un algoritmo eficiente tanto en términos de
tiempo como de uso de memoria, adecuado para una amplia gama de aplicaciones en el análisis
de datos.

Referencias
Búsqueda binaria (artículo). (s/f). Khan Academy. Recuperado el 1 de agosto de 2024, de
https://es.khanacademy.org/computing/computer-science/algorithms/binary-search/a/binary-
search

Navarro, A. (2016, octubre 31). Ordenamiento por inserción - Algoritmos de ordenamiento.

Junco TIC. https://juncotic.com/ordenamiento-por-insercion-algoritmos-de-ordenamiento/

22