a) Objetivo
El algoritmo QuickSort desarrolla una estrategia de "divide y conquista" para ordenar un
arreglo de elementos. La idea principal es seleccionar un elemento del arreglo como pivote
y reorganizar los elementos de manera que los elementos menores que el pivote estén a su
izquierda y los elementos mayores estén a su derecha. Luego, el algoritmo se aplica
recursivamente a las dos mitades del arreglo generadas por el pivote. Este proceso
continúa hasta que todas las particiones contienen un solo elemento, momento en el que el
arreglo está completamente ordenado.
En cada iteración del algoritmo, se elige un pivote, se particiona el arreglo y se ordenan las
dos sub-particiones. El pivote puede ser seleccionado de varias maneras, pero comúnmente
se elige el último elemento del arreglo. Una vez que el pivote se coloca en su posición final,
todos los elementos menores que él están a su izquierda y todos los elementos mayores
están a su derecha. Esto se logra utilizando dos índices, uno que avanza desde el principio
del arreglo y otro que retrocede desde el final, intercambiando los elementos según sea
necesario.
b) Indicar que datos de entrada requiere el algoritmo y qué datos saldrán.
El algoritmo QuickSort requiere un arreglo de elementos como entrada. Estos elementos
pueden ser números, cadenas u otros tipos de datos que sean comparables entre sí para
determinar su orden relativo. No hay requisitos especiales sobre el tamaño mínimo o
máximo del arreglo, pero debe contener al menos un elemento para que el algoritmo
funcione.
Como salida, el algoritmo QuickSort proporcionará el mismo arreglo de entrada, pero
ordenado en orden ascendente o descendente, según el criterio especificado. Es decir, los
elementos del arreglo estarán reorganizados de manera que estén en orden de menor a
mayor (o de mayor a menor). La salida será un arreglo que contiene los mismos elementos
que el arreglo de entrada, pero ordenados de acuerdo con el algoritmo QuickSort.
c) Listado de las funciones que usa el algoritmo.
El algoritmo QuickSort utiliza las siguientes funciones:
1. *partition(arr, low, high)*:
- Esta función toma un arreglo arr y dos índices low y high que representan el rango del
arreglo que se está considerando.
- Selecciona un pivote de arr[high].
- Reorganiza los elementos del arreglo de manera que los elementos menores que el
pivote estén a su izquierda y los mayores a su derecha.
- Devuelve el índice del pivote después de la partición.
2. *quicksort(arr, low, high)*:
- Esta función implementa el algoritmo de QuickSort utilizando recursión.
- Recibe un arreglo arr y dos índices low y high que representan el rango del arreglo que
se está considerando.
- Selecciona un pivote utilizando la función partition y llama recursivamente a quicksort en
las dos mitades del arreglo generadas por el pivote.
3. *visualize_quicksort(arr)*:
- Esta función se encarga de la visualización del proceso de ordenación utilizando
Matplotlib.
- Crea una gráfica de barras que representa el arreglo arr.
- Llama a la función quicksort para ordenar el arreglo y actualiza la gráfica en cada paso
de la ordenación.
4. *update_plot(array)*:
- Esta función actualiza la gráfica de barras con el estado actual del arreglo durante el
proceso de ordenación.
- Recibe un arreglo array y actualiza la altura de las barras en la gráfica correspondiente.
- Destaca el pivote actual en la gráfica cambiando su color a azul.
Cada una de estas funciones tiene un papel específico en el algoritmo QuickSort: la
partición del arreglo, la recursión para ordenar las sub-particiones y la visualización del
proceso de ordenación.
d) Determinar qué funciones son recursivas y cuáles no
e) Modelos matemáticos que emplea el algoritmo
