Ordenación rápida como un método de programación

En 1960, K. A. Hoar desarrolló un método para la clasificación rápida de la información, se convirtió en el más famoso. Hoy en día es ampliamente utilizado en la programación, ya que tiene muchas propiedades positivas: se puede utilizar para los casos generales, se requiere un pequeño aumento en la memoria adicional, compatible con diferentes tipos de listas y fácil de implementar. Pero también hay desventajas, que tiene la ordenación rápida: el uso de trabajo permitió un montón de errores, y es algo inestable.

Sin embargo, es la versión más estudiado. Después de la primera Hoare pago, muchos hacen su estudio denso. base grande se estableció en cuestiones teóricas de encontrar el tiempo empleado en el trabajo, que se basa en la evidencia empírica. Hubo propuestas reales para mejorar el algoritmo básico y una mayor velocidad.

Ordenación rápida es muy común, que se puede encontrar en todas partes. En su base, el método se implementa TList.Sort, presente en todas las versiones (excepto 1) Delphi, la función de biblioteca de tiempo que tomó para completar, qsort en C ++.

El principio básico de funcionamiento se puede formular como un "divide y vencerás". Ocurre romper la lista en dos grupos y se clasifican para cada parte por sí mismo. Se deduce que más se debe prestar atención al proceso de separación, durante el cual se produce la siguiente: se determina por un elemento de base y relativamente ha reorganizado toda su lista. Construido a la izquierda de un grupo de candidatos, cuyo valor es menor que el resto de las reglas de transferencia. Resulta que el principal elemento en la lista ordenada está en su lugar que le corresponde. La siguiente etapa – un desafío funciones de clasificación recursivo para ambos lados de los elementos relativos a la base. Se termina el proceso sólo funciona si la lista contiene sólo un elemento, es decir que ser resuelto. Por lo tanto, con el fin de dominar una función de programación como una especie rápida, es necesario conocer el trabajo de los algoritmos de bajo nivel: a) la elección del miembro de base; b) una lista de la permutación más eficaz para producir dos conjuntos con valores más pequeños y más grandes.

Familiarizarse con los primeros principios. Al elegir el elemento de base, idealmente debe ser seleccionado de la lista de la media. A continuación, en el descanso se divide en dos mitades iguales. Sólo calcular el valor medio de la lista es muy difícil, por lo que incluso el más rápido de clasificación no pasa por este lado cálculo. Pero la elección del elemento básico con el valor máximo o mínimo – tampoco la mejor opción. En tal caso, la determinación de un solo crea estarán garantizadas listas vacías, y la segunda completa. Por lo tanto la conclusión de que como el miembro de base debe ser elegido uno que está más cercano a la media, pero en el máximo y el mínimo.

Una vez que se determina una elección, se puede proceder con el algoritmo de descomposición. Este llamado bucles internos ordenación rápida. Todo está construido en dos índices de acceso rápido: en primer lugar ir a través de los elementos de izquierda a derecha, el segundo, por el contrario, de derecha a izquierda. Comienza la operación se ejecute la derecha: el índice se encuentra en la lista y comparar todos los valores de la principal. El ciclo se completa cuando el elemento es menor que o igual a la línea base. Es decir, no es una comparación y disminuye el valor del índice. En la mano izquierda cuando el trabajo está terminado mayor o igual valor. En este caso, el valor de comparación se incrementa.

En esta etapa del algoritmo de partición que comprende quicksort, pueden surgir dos situaciones. La primera es que el índice de la izquierda es inferior a la derecha. Esto indica un error, entonces hay elementos en los que se indica en la lista están en el orden equivocado. Salida – cambiar sus lugares. La segunda situación es cuando tanto de la columna es igual o cruzado. Esto indica una separación exitosa de la lista, es decir, el trabajo se ha completado.