A continuación, se analizan cuatro algoritmos; dos para ordenamiento: el ordenamiento burbuja y el MergeSort; los otros dos algoritmos de búsqueda: La busqueda lineal o secuencial y la búsqueda binaria.
Este proyecto implementa y compara cuatro algoritmos estudiados en la Unidad 4:
- Ordenamiento Burbuja (
bubble_sort) - Merge Sort (
merge_sort) - Búsqueda lineal (
busqueda_lineal) - Búsqueda binaria (
busqueda_binaria) El objetivo del proyecto es analizar la eficiencia de estos algoritmos y comparar las complejidades teóricas planteadas en R1 con los tiempos reales de ejecución obtenidos experimentalmente en R4. Para las pruebas se utilizan listas generadas aleatoriamente con los siguientes tamaños: - 1.000 elementos
- 2.000 elementos
- 4.000 elementos
- 8.000 elementos
time.perf_counter()
Además, se calcula la razón entre cada medición y la medición anterior mediante:
Razón = Tiempo actual / Tiempo anterior
Esto permite analizar cómo aumenta el tiempo de ejecución cuando se duplica el tamaño de la entrada.
El proyecto está organizado de la siguiente manera:
apellido_nombre_AlgEstDatos_U4/
│
├── main.py
├── metodos_ordenamiento.py
├── busquedas.py
└── README.md
Es el programa principal encargado de efectuar las pruebas de la siguiente manera:
- Generar las listas de números aleatorios.
- Ejecutar los algoritmos.
- Medir los tiempos de ejecución.
- Calcular las razones entre mediciones.
- Mostrar los resultados en la consola.
Contiene los algoritmos de ordenamiento:
bubble_sort()
merge_sort()Donde:
bubble_sort() implementa el método de ordenamiento Burbuja.
merge_sort() implementa Merge Sort utilizando el principio de dividir la lista en partes más pequeñas y posteriormente fusionarlas.
Contiene los dos algoritmos de búsqueda:
busqueda_lineal()
busqueda_binaria()Donde:
La búsqueda lineal recorre los elementos de la lista uno por uno hasta localizar el objetivo.
La búsqueda binaria divide sucesivamente el intervalo de búsqueda a la mitad. Este algoritmo requiere como precondición que la lista esté previamente ordenada.
Para cumplir esta condición, en main.py la lista utilizada por la búsqueda binaria se ordena previamente mediante MergeSort.
Para ejecutar el proyecto se necesita:
- Python 3
- No se requieren librerías externas. El programa utiliza únicamente módulos pertenecientes a la biblioteca estándar de Python:
import random
import timeDescargue el repositorio de GitHub.
Los siguientes archivos deben encontrarse dentro de la misma carpeta:
main.py
metodos_ordenamiento.py
busquedas.py
README.md
Ubíquese desde la terminal o consola en la carpeta donde se encuentran los archivos.
Ejecute:
python main.pyDependiendo de la configuración del sistema también puede utilizarse:
python3 main.pyEl programa ejecutará automáticamente las pruebas correspondientes a los cuatro algoritmos y mostrará los resultados en pantalla.
Los algoritmos utilizados en este laboratorio son:
Algoritmo simple que compara elementos adyacentes y realiza intercambios cuando estos se encuentran en el orden incorrecto.
Algoritmo eficiente que divide recursivamente la lista en dos partes y posteriormente fusiona las partes ordenadas.
Recorre secuencialmente la lista hasta encontrar el elemento buscado.
Busca el elemento dividiendo repetidamente el intervalo de búsqueda a la mitad. La búsqueda binaria requiere que la lista esté previamente ordenada.
| Algoritmo | Mejor caso | Caso promedio | Peor caso | Espacial |
|---|---|---|---|---|
| Burbuja | O(n) | O(n²) | O(n²) | O(1) |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) |
| Búsqueda lineal | O(1) | O(n) | O(n) | O(1) |
| Búsqueda binaria | O(log n) | O(log n) | O(log n) | O(1) |
Las mediciones experimentales se realizan utilizando los siguientes tamaños:
tamanos = [1000, 2000, 4000, 8000]Los resultados registrados durante las pruebas fueron los siguientes:
| Algoritmo | n | Tiempo (s) | Razón |
|---|---|---|---|
| Burbuja | 1000 | 0.03765077 | - |
| Burbuja | 2000 | 0.15185097 | 4.03 |
| Burbuja | 4000 | 0.62407692 | 4.11 |
| Burbuja | 8000 | 2.53522649 | 4.06 |
| Merge Sort | 1000 | 0.00117464 | - |
| Merge Sort | 2000 | 0.00307395 | 2.62 |
| Merge Sort | 4000 | 0.00520382 | 1.69 |
| Merge Sort | 8000 | 0.01229026 | 2.36 |
| Búsqueda lineal | 1000 | 0.00003293 | - |
| Búsqueda lineal | 2000 | 0.00005901 | 1.79 |
| Búsqueda lineal | 4000 | 0.00011725 | 1.99 |
| Búsqueda lineal | 8000 | 0.00023693 | 2.02 |
| Búsqueda binaria | 1000 | 0.00000467 | - |
| Búsqueda binaria | 2000 | 0.00000399 | 0.85 |
| Búsqueda binaria | 4000 | 0.00000260 | 0.65 |
| Búsqueda binaria | 8000 | 0.00000430 | 1.65 |
Los tiempos pueden presentar pequeñas variaciones entre diferentes ejecuciones debido al equipo utilizado, el sistema operativo, la carga del procesador y la generación aleatoria de los datos.
Las razones obtenidas fueron:
4.03
4.11
4.06
Cuando el tamaño de la entrada se duplica, el tiempo de ejecución aumenta aproximadamente cuatro veces. Este resultado coincide con la complejidad teórica:
O(n²)
Las razones obtenidas fueron:
2.62
1.69
2.36
El crecimiento observado es considerablemente menor que el presentado por el algoritmo Burbuja. En términos generales, los resultados son compatibles con la complejidad:
O(n log n)
Las variaciones pueden estar relacionadas con la recursión, la asignación de memoria y el ruido normal de las mediciones. Por lo tanto, la predicción de R1 se cumple en términos generales.
Las razones obtenidas fueron:
1.79
1.99
2.02
En las pruebas se selecciona como objetivo el último elemento de la lista, obligando al algoritmo a recorrer prácticamente todos sus elementos. Al duplicar el tamaño de la entrada, el tiempo tiende aproximadamente a duplicarse. Este comportamiento coincide con:
O(n)
Las razones obtenidas fueron:
0.85
0.65
1.65
Los tiempos registrados para este algoritmo son extremadamente pequeños, del orden de pocos microsegundos. Por esta razón, factores como:
- Costos constantes de ejecución.
- Resolución de la medición.
- Procesos del sistema operativo.
- Carga del procesador. pueden tener una influencia importante sobre los resultados. A pesar de las variaciones de las razones, el tiempo de ejecución permanece prácticamente constante al aumentar el tamaño de la lista. Los resultados son compatibles con el comportamiento esperado:
O(log n)
Se debe tener en cuenta que una sola ejecución no permite observar claramente el crecimiento logarítmico.
Los resultados experimentales obtenidos en R4 respaldan, en términos generales, las predicciones realizadas en R1.