Algoritmo Quicksort y Selección de Pivote

Selección de pivote en Quicksort

• El primer elemento de la lista se elige como pivote.
• Se utiliza un proceso de particionado para dividir los elementos en tres listas: mayores, menores e iguales al pivote.
• Las listas 'menores' y 'mayores' se ordenan recursivamente y luego se concatanen con la lista 'igual'.

Función Recursiva

• Las funciones recursivas se llaman a sí mismas, útiles para problemas con estructura jerárquica.
• Estrategia de divide y vencerás es efectiva para resolver problemas complejos.

Problema 1: Función de Suma

• Función: my_sum, recibe una lista y calcula la suma de sus elementos.
• No usar la función sum de Python.
• Implementación se puede hacer con recursión o iteración.

Polinomios de Chebyshev

• Se definen de manera recursiva, divididos en dos tipos: primera y segunda clase.
• Primer tipo: Tn(x) con relación de recurrencia Tn(x) = 2xTn−1(x) − Tn−2(x).
• Casos base: T0(x) = 1, T1(x) = x.
• Segundo tipo: Un(x) con relación de recurrencia Un(x) = 2xUn−1(x) − Un−2(x) y casos base U0(x) = 1, U1(x) = 2x.

Problema 3: Función de Ackermann

• Definida por una relación recursiva, se caracteriza por su rápido crecimiento.
• Función: my_ackermann(m,n) para calcular el máximo común divisor.
• Relación recursiva para el gcd: si b es 0, gcd(a,b) = a; de lo contrario, gcd(a,b) = gcd(b, a%b).

Triángulo de Pascal

• Disposición de números donde cada fila equivale a los coeficientes de la expansión binomial.
• Relación recursiva para obtener elementos: Rm(i) = Rm-1(i-1) + Rm-1(i) para i = 2,...,m-1.
• Función: my_pascal_row(m) para generar la fila m.

Problema 9: Matriz Espiral

• Función: my_spiral_ones(n) genera una matriz n x n con unos formando una espiral.
• Los unos siguen un patrón: van a la derecha, luego hacia abajo, hacia la izquierda y finalmente hacia arriba.

Función Combinatoria C(n, k)

• Calcula cuántas formas hay para elegir k elementos de n sin repetición.
• Usos comunes en estadística.
• Casos especiales incluyen: si n = k, entonces C(n, k) = 1, y si k = 1, C(n, k) = n.

Problema 5: Cambio

• Definición: devolución de dinero en transacciones en efectivo.
• Utiliza una relación recursiva para determinar billetes y monedas necesarios.
• Denominaciones de la moneda estadounidense: 100, 50, 20, 10, 5, 1, 0.25, 0.10, 0.05, 0.01.

Problema 6: Número Áureo

• El número áureo (φ) es el límite de F(n+1) cuando n tiende a infinito, aproximadamente 1.62.
• Representación de fracción continua representa φ.
• Función recursiva: my_golden_ratio(n) para obtener la aproximación del número áureo en su n-ésima iteración.

Este cuestionario abarca el algoritmo Quicksort, centrándose en la selección del pivote y cómo se realizan las particiones. Aprenderás sobre la clasificación recursiva de listas y cómo los elementos se distribuyen en listas más pequeñas, del mismo tamaño y más grandes. ¡Pon a prueba tus conocimientos sobre algoritmos de ordenamiento!