Entendiendo el Algoritmo de Ordenamiento QuickSort
Hoy profundicé en el algoritmo QuickSort y finalmente comprendo por qué es tan eficiente. La clave está en la estrategia "divide y vencerás" y la elección del pivote.
💡 Lo que aprendí:
QuickSort tiene una complejidad promedio de O(n log n), pero puede degradarse a O(n²) en el peor caso si el pivote no se elige correctamente. Implementar la versión aleatoria del pivote reduce significativamente este riesgo.
function quickSort(arr) {
if (arr.length <= 1) return arr;
const pivot = arr[Math.floor(Math.random() * arr.length)];
const left = arr.filter(x => x < pivot);
const middle = arr.filter(x => x === pivot);
const right = arr.filter(x => x > pivot);
return [...quickSort(left), ...middle, ...quickSort(right)];
}