¿Qué es Quick Sort?

Quick Sort (ordenamiento rápido) es un algoritmo eficiente de ordenamiento basado en el enfoque de "divide y vencerás". Selecciona un elemento llamado "pivote" y organiza el arreglo de forma que todos los elementos menores al pivote queden a su izquierda y los mayores a su derecha. Luego aplica este proceso de manera recursiva.

El Código

                
function quickSort(arr) {
  if (arr.length <= 1) {
    return arr;
  }

  const pivot = arr[arr.length - 1];
  const left = [];
  const right = [];

  for (const el of arr.slice(0, arr.length - 1)) {
    if (el < pivot) {
      left.push(el);
    } else {
      right.push(el);
    }
  }

  return [...quickSort(left), pivot, ...quickSort(right)];
}

// Ejemplo de uso
const array = [34, 7, 23, 32, 5, 62];
console.log("Array ordenado:", quickSort(array));
                
            

Puntos Clave del Algoritmo

• Entrada: Un arreglo desordenado (arr).
• Salida: El arreglo ordenado de menor a mayor.
• Método:
  • Selecciona un elemento como pivote (en este caso, el último del arreglo).
  • Divide el arreglo en dos subarreglos: uno con elementos menores al pivote y otro con elementos mayores.
  • Ordena recursivamente los subarreglos y combina los resultados.
• Complejidad:
  • Peor caso: O(n²), ocurre cuando el pivote siempre es el elemento más grande o más pequeño.
  • Mejor caso: O(n log n), ocurre cuando el pivote divide el arreglo en partes iguales.
  • Promedio: O(n log n).
• Ventajas: Es eficiente y no requiere espacio adicional significativo.
• Desventajas: El rendimiento puede ser inconsistente dependiendo de cómo se selecciona el pivote.

Ejemplo de Ejecución

Arreglo inicial: [34, 7, 23, 32, 5, 62]

Proceso de ordenamiento:

1. Selecciona el pivote: 62. Particiona en [34, 7, 23, 32, 5] y [].
2. Selecciona el pivote: 5. Particiona en [] y [34, 7, 23, 32].
3. Selecciona el pivote: 32. Particiona en [23, 7] y [34].
4. Selecciona el pivote: 7. Particiona en [] y [23].

Resultado final: [5, 7, 23, 32, 34, 62]

Información Adicional

Quick Sort es ampliamente utilizado debido a su alta eficiencia y flexibilidad. Aunque su rendimiento puede ser afectado por la elección del pivote, su implementación básica es adecuada para la mayoría de las aplicaciones prácticas.