img img
Burbuja Inserción Selección MergeSort QuickSort

Algoritmo QuickSort

Consiste en seleccionar un elemento de la lista, llamado pivoteIdx, y luego reorganizar los elementos de la lista de manera que todos los elementos menores que el pivoteIdx estén a su izquierda, y todos los elementos mayores estén a su derecha. Después de esta partición, el pivoteIdx está en su posición final. Luego, el algoritmo se aplica recursivamente a las sublistas generadas por la partición hasta que toda la lista esté ordenada.

Ventajas:

  • Tiempo de ejecución: Es uno de los algoritmos más rápidos conocidos.
  • Memoria: No requiere memoria adicional en su forma recursiva.
  • Adaptación: Requiere de pocos recursos en comparación a otros métodos de ordenamiento.

Desventajas:

  • Dificultad: Es un poco más difícil de implementar que los algoritmos promedio.
  • Rendimiento: Existe una gran diferencia entre el mejor y el peor caso.
  • No estable: No preserva el orden relativo de elementos con claves iguales.

Demostración del Algoritmo

Instrucciones:

1. Ingresar valores numéricos del 1 al 10.
2. Se necesitan por lo menos 3 valores para poder ser ordenados.
3. Presione "Aleatorio" para generar valores al azar.
4. Cada valor corresponde al tamaño de las barras en el gráfico.
5. Cuando una barra se colorea de amarillo corresponde al pivote.
6. Cuando las barras se colorean de rojo es porque se está recorriendo la gráfica para proceder a ordenarlos.
7. Las barras que se colorean de verde son las que se intercambiarán para ser ordenadas.
8. Presione "Ordenar" para ejecutar el algoritmo y ordenar los valores de forma ascendente.
9. Presione "Limpiar" para borrar el gráfico.

Código:

function quickSort(arreglo, izquierda=0, derecha=arreglo.length-1){
    if(izquierda < derecha){
        const pivoteIdx = particion(arreglo, izquierda, derecha);
        quickSort(arreglo, izquierda, pivoteIdx-1);
        quickSort(arreglo, pivoteIdx+1, derecha);
    }
    return arreglo;
}
    
function particion(arreglo, izquierda, derecha){
    const pivote = arreglo[derecha];
    let i = izquierda-1;
    for(let j=izquierda; j < derecha; j++){
        if(arreglo[j] <= pivote){
            i++;
            [arreglo[i], arreglo[j]] = [arreglo[j], arreglo[i]];
        }
    }
    [arreglo[i+1], arreglo[derecha]] = [arreglo[derecha], arreglo[i+1]];
    return i+1;
}