Universidad Nacional de Trujillo
Facultad de Ciencias Físicas y Matemáticas – Ingeniería Informática
Tema: QuickSort
Curso: Algoritmos y Complejidad
Docente: Daniel Augusto Alvarez Campos
Alumna : Chilon Mendoza Andrea Cristina
Modalidad: Individual – Duración: 1 hora
Valle Jequetepeque- Guadalupe –26/09/2025
Informe de Laboratorio en Excel – QuickSort (Grupo 1)
Introducción
En este laboratorio se analiza el algoritmo QuickSort en dos escenarios: el mejor caso
(cuando las particiones son equilibradas) y el peor caso (cuando las particiones son
desbalanceadas). El objetivo es comprender cómo la complejidad de QuickSort puede variar
entre O(n log n) y O(n²). Para ello, se construyen los árboles de recurrencia en Excel, se
generan tablas, se comparan los resultados con las fórmulas teóricas y se elaboran
conclusiones.
Desarrollo del laboratorio
1. Complete la hoja 'mejor' con las fórmulas correspondientes. Tome capturas de
pantalla mostrando la tabla y el gráfico de trabajo por nivel.
Tamaño inicial=128
Tamaño inicial=256
Tamaño inicial=512
Tamaño inicial=1024
Tamaño inicial=2048
2. Complete la hoja 'peor'. Incluya capturas de pantalla de la tabla y el gráfico del costo
acumulado.
Tamaño inicial=128
Tamaño inicial=256
Tamaño inicial=512
Tamaño inicial=1024
Tamaño inicial=2048
3. En la hoja 'comparativa', pegue los valores acumulados, compare con las fórmulas
teóricas y genere el gráfico de las tres curvas. Incluya capturas de pantalla de esta hoja.
Mejor Caso
Peor Caso
Preguntas de análisis
1. ¿Por qué en el mejor caso QuickSort tiene costo O(n log n)?
En el mejor caso, QuickSort divide el arreglo en dos partes iguales en cada paso, logrando
una recursión logarítmica (O(log n)). Como en cada nivel se comparan todos los
elementos, el trabajo por nivel es O(n). Al combinar ambos, el tiempo total de ejecución
es O(n log n), ya que hay log(n) niveles y en cada nivel se hace trabajo sobre todos los
elementos.
2. ¿Por qué en el peor caso QuickSort se degrada a O(n²)?
En el peor caso, cuando el pivote seleccionado no divide bien el arreglo (por ejemplo,
siempre el menor o mayor elemento), QuickSort se convierte en una búsqueda lineal. En
lugar de dividir el problema a la mitad, se reduce a solo un subarreglo por nivel, lo que
lleva a O(n) niveles de recursión, y en cada nivel se realiza O(n) trabajo, resultando en
O(n²).
3. ¿Cómo se refleja esto en los gráficos de Excel?
En el gráfico del major caso, la curva es más suave y crece de manera controlada,
siguiendo la tendencia de O(n log n). Por otro lado, en el peor caso, el gráfico muestra un
crecimiento más rápido y pronunciado, ya que el costo sigue una curva cuadrática O(n²),
reflejando el comportamiento ineficiente del algoritmo.
4. ¿Qué estrategias existen para evitar el peor caso de QuickSort?
Seleccionar el pivote aleatoriamente, lo que reduce la probabilidad de tener un
arreglo desbalanceado.
Usar la mediana de tres, donde el pivote es el valor mediano de tres elementos (el
primero, el último y el del medio).
Usar Insertion Sort en subarreglos pequeños, ya que este algoritmo es más
eficiente en arreglos pequeños y evita la degradación de QuickSort.
5. ¿En qué situaciones prácticas QuickSort resulta más eficiente que MergeSort?
QuickSort es más eficiente que MergeSort en situaciones donde el uso de memoria es
limitado, ya que QuickSort es un algoritmo in-place, lo que significa que no requiere
espacio extra. También es más rápido en la práctica en arreglos grandes o casi
ordenados, debido a su menor sobrecarga en comparación con MergeSort, que tiene
una mayor necesidad de memoria debido a su enfoque de dividir y conquistar con
arreglos auxiliares.
Conclusiones
Mejor Caso:
En el mejor caso, QuickSort tiene un rendimiento de O(n log n) cuando el pivote divide el arreglo
de manera equilibrada. Esto permite que el algoritmo sea eficiente y rápido, pero depende de
que el pivote sea seleccionado correctamente.
Peor Caso:
En el peor caso, si el pivote no es adecuado (como el menor o mayor elemento), QuickSort se
degrada a O(n²). Esto sucede porque el arreglo no se divide bien, lo que genera una recursión
innecesaria y mucho trabajo extra.
Ventajas:
Eficiencia en promedio: Rápido en la mayoría de los casos con O(n log n).
Memoria eficiente: No requiere espacio adicional, ya que es in-place.
Rendimiento en grandes volúmenes de datos: Suele ser más rápido que MergeSort.
Limitaciones:
Peor caso O(n²): Si no se elige bien el pivote, el rendimiento se degrada.
Inestabilidad: No mantiene el orden relativo de elementos iguales.
Dependencia del pivote: El rendimiento depende mucho de cómo se elija el pivote.
QuickSort es eficiente en promedio, pero su rendimiento puede variar dependiendo de cómo se
elijan los pivotes. Con precauciones, como la selección aleatoria del pivote, puede ser una
excelente opción, pero debe usarse con cuidado para evitar el peor caso.
Rúbrica de Evaluación (0–20 puntos)
• Hoja 'mejor' completada y coherente con fórmulas: 3 pts
• Capturas claras de la hoja 'mejor': 1 pt
• Hoja 'peor' completada y coherente con fórmulas: 3 pts
• Capturas claras de la hoja 'peor': 1 pt
• Hoja 'comparativa' con valores correctos: 2 pts
• Gráfico comparativo con las tres curvas: 2 pts
• Respuestas a preguntas de análisis: 3 pts
• Conclusiones bien redactadas y críticas: 3 pts
• Presentación formal (portada, ortografía, orden): 2 pts