En el Capítulo 5, viste un método de clasificación simple llamado
clasificación de burbujas. Se mencionó en ese momento que hay
calificaciones significativamente mejores. Aquí desarrollará una versión de uno de los mejores: clasificación rápida (Quicksort).
Clasificación rápida, inventada y nombrada por C.A.R. Hoare, es el mejor algoritmo de clasificación de propósito general disponible actualmente. No pude mostrarlo en el Capítulo 5 porque la mejor implementación de clasificación rápida se basa en la recursividad. La versión que desarrollaremos ordena una serie de caracteres, pero la lógica se puede adaptar para ordenar cualquier tipo de objeto.
La clasificación rápida se basa en la idea de particiones. El procedimiento general implica seleccionar un valor, llamado comparar, y luego dividir la matriz en dos secciones. Todos los elementos mayores o iguales al valor de la partición se insertan en un lado y los más pequeños en el otro. Este proceso se repite para cada sección restante hasta que se ordene la matriz. Por ejemplo, dada la matriz fedacb y usando el valor d como comparación, el primer paso de clasificación rápida reorganizaría la matriz como se muestra a continuación:

F e d a c b inicial
Pasaje 1 b c a d e f

Este proceso se repite para cada sección, es decir, bca y def. Como puede ver, el proceso es esencialmente recursivo por naturaleza y, de hecho, la implementación más limpia de clasificación rápida es recursiva.
Puede seleccionar el valor de comparación de dos maneras. Puedes seleccionarlo aleatoriamente o encontrando el promedio de un pequeño conjunto de valores tomados de la matriz. Para obtener una clasificación óptima, debe seleccionar un valor que esté exactamente en el medio del rango de valores. Sin embargo, no es fácil hacer esto para la mayoría de los conjuntos de datos. El peor caso es cuando el valor seleccionado está en un extremo. Aun así, la clasificación rápida se ejecutará correctamente.
La versión de clasificación rápida que desarrollaremos selecciona el elemento central de la matriz como comparación.

Consulte QSDemo.java.

Clasificación rápida:

• Uno de los algoritmos de clasificación más eficientes y utilizados.
• Inventado por C.A.R. Ronco.
• Basado en el concepto de particiones, donde la matriz se divide en secciones que se ordenan de forma recursiva.
• Más eficiente que la clasificación por burbujas y otros métodos simples.

Operación:

• Valor de comparación (pivote):
• Se elige un valor como referencia (pivote) y la matriz se organiza alrededor de ese valor.
• Los elementos más pequeños que el pivote van hacia un lado y los más grandes hacia el otro.
• El proceso se repite recursivamente para cada sección hasta que la matriz esté completamente ordenada.

clasificación rápida

Demostración QSD