В 1960 году К. А.Hoar ha desarrollado un método para clasificar rápidamente la información, que se ha convertido en el más famoso. Hoy en día se usa ampliamente en programación, ya que tiene muchas propiedades positivas: se puede usar para casos generales, requiere un pequeño aumento de memoria adicional, es compatible con diferentes tipos de listas y es conveniente para la implementación. Pero también hay desventajas que tiene la clasificación rápida: cuando se usa en el trabajo, se cometen muchos errores y es algo inestable.
Sin embargo, esta es la versión más estudiada.Después de la aparición de los primeros cálculos de Hoar, muchos comenzaron a estudiarlo de cerca. Se creó una gran base sobre las cuestiones teóricas de encontrar el tiempo dedicado al trabajo, que fue respaldado por datos empíricos. Hubo sugerencias reales para mejorar el algoritmo básico y aumentar la velocidad del trabajo.
La clasificación rápida es muy común, puede serreunirse en todas partes. Sobre esta base, se implementa el método TList.Sort, que existe en todas las versiones (excepto 1) de Delphi, una función de la biblioteca del tiempo dedicado a la ejecución, qsort en C ++.
El principio básico del trabajo puede formularse como"divide y vencerás". La lista se divide en dos grupos y la clasificación se realiza para cada parte por sí misma. De ello se deduce que se debe prestar más atención al proceso de separación, durante el cual ocurre lo siguiente: se determina el elemento básico y se reorganiza toda la lista en relación con él. A la izquierda hay un grupo de candidatos cuyos valores son más pequeños, a la derecha se transfieren todos los demás. Resulta que el elemento principal en la lista ordenada se encuentra en el lugar que le corresponde. El siguiente paso es llamar a la función de ordenación recursiva para ambos lados de los elementos en relación con la base. El proceso de trabajo finaliza solo cuando la lista contiene solo un elemento, es decir, se ordenará. Por lo tanto, para dominar una función de programación como la clasificación rápida, debe conocer el funcionamiento de los algoritmos de nivel inferior: a) la elección de un elemento básico; b) la permutación más eficiente de la lista para obtener dos conjuntos con valores cada vez más pequeños.
Conozcamos los principios de la primera.Al elegir un elemento base, idealmente, el medio debe seleccionarse de la lista. Luego, cuando se rompa, se dividirá en dos mitades iguales. Solo es muy difícil calcular el valor promedio en la lista, por lo que incluso la clasificación más rápida omite este cálculo. Pero también la elección del elemento principal con un valor máximo o mínimo tampoco es la mejor opción. En el caso de tal definición, se garantizará que una de las listas creadas esté vacía, y la segunda estará llena. De ahí la conclusión de que, como elemento base, debe elegir uno que esté más cerca del promedio, pero más alejado del máximo y el mínimo.
Una vez que haya hecho su elección, puedevaya a la operación del algoritmo de partición. Estos son los llamados ciclos internos de clasificación rápida. Todo se basa en dos índices de rápido rendimiento: el primero pasará por los elementos de izquierda a derecha, el segundo, por el contrario, de derecha a izquierda. Comienza la operación de ejecución a la derecha: el índice recorre la lista y compara todos los valores con el principal. Un ciclo se considera completo si hay un elemento menor o igual que la base. Es decir, se produce una comparación y el valor del índice disminuye. En el lado izquierdo, el trabajo se completa al encontrar un valor mayor o igual. Y aquí el valor al comparar aumenta.
En esta etapa del algoritmo de partición,que contiene quicksort, pueden surgir dos situaciones. El primero es que el índice de la izquierda será menor que el de la derecha. Esto indica un error, es decir, los elementos que se señalaron están en la lista en el orden incorrecto. La salida es cambiar sus lugares. La segunda situación es cuando ambas columnas son iguales o intersectadas. Esto indica una separación exitosa de la lista, es decir, el trabajo puede considerarse terminado.
