SincroDev Quick Sort: El Rey de la Velocidad y el "Divide y Vencerás"
Si tienes que apostar por un algoritmo de ordenamiento en una carrera, apuesta por Quick Sort. Desarrollado por Tony Hoare en 1959, sigue siendo el estándar de facto en muchas librerías estándar de lenguajes de programación.
La Estrategia: Divide y Vencerás
Quick Sort no intenta ordenar toda la lista de golpe. Su estrategia es más política: divide el problema en problemas más pequeños.
- Elegir un Pivote: Selecciona un elemento del array (puede ser el primero, el último, o uno al azar).
- Particionar: Reorganiza el array de modo que:
- Todos los elementos menores que el pivote queden a su izquierda.
- Todos los elementos mayores queden a su derecha.
- Recursividad: Ahora tienes dos sub-listas (izquierda y derecha). Aplicas el mismo proceso a cada una.
Cuando las sub-listas son de tamaño 0 o 1, ¡ya están ordenadas!
🏁 Carrera de Algoritmos
Mismo set de datos (50 elementos). ¿Quién gana?
El Código (Conceptual)
def quick_sort(arr):
if len(arr) <= 1:
return arr
pivote = arr[len(arr) // 2]
izquierda = [x for x in arr if x < pivote]
centro = [x for x in arr if x == pivote]
derecha = [x for x in arr if x > pivote]
return quick_sort(izquierda) + centro + quick_sort(derecha)¿Por qué es tan rápido?
Aunque su complejidad teórica promedio es O(n log n) (igual que Heap Sort), en la práctica Quick Sort suele ganar. Esto se debe a que tiene un bucle interior muy simple y aprovecha muy bien la caché de la CPU al trabajar con elementos contiguos en memoria.
El Talón de Aquiles
Tiene un “pero”: en el peor caso (si eliges muy mal el pivote, por ejemplo, si la lista ya está ordenada y tomas siempre el primero), su rendimiento cae a O(n²), igual que Bubble Sort. Sin embargo, con buenas estrategias de elección de pivote (como elegir la mediana), esto es estadísticamente improbable.