La ordenación rápida es bastante similar a la ordenación por fusión en el sentido de que este algoritmo ayuda a los programadores a dividir y conquistar. Escoge elementos como pivote, después de lo cual crea particiones en el array. Quick sort tiene numerosas versiones y cada una de ellas elige el pivote de forma diferente.

El comando partition() es posiblemente la parte más importante de la ordenación rápida. Los objetivos de partición reciben un array junto con un elemento del array x como pivote. Hay que colocar la x en la posición correcta, que es el array ordenado, a la que seguirá la colocación de elementos menores que x antes de ella. Por último, tienes que colocar los elementos más grandes que x después de ella. Asegúrate de hacer todo esto en tiempo lineal.

También hay que tener en cuenta que quick sort crea particiones en los arrays, tras lo cual se llama a sí mismo en repetición dos veces para ordenar los subarrayas resultantes. Un algoritmo como éste resulta increíblemente útil para conjuntos de datos grandes. Esto se debe a que O(n2) son sus complejidades en el peor de los casos. Los dos términos iniciales están ahí para las llamadas recursivas, mientras que el término final resulta útil en el proceso de partición. Los elementos más pequeños que el pivote están representados por k.

El tiempo que tarda la ordenación rápida suele depender de la estrategia de partición, junto con el array de entrada.

Los tres casos de ordenación rápida

Al igual que otros algoritmos de ordenación, la ordenación rápida también tiene casos. Vamos a discutirlos a continuación:

El peor caso

Este tipo de caso tiene lugar cuando el proceso de partición elige el elemento más pequeño o más grande como pivote. Considerando la estrategia de partición discutida anteriormente, donde el último elemento es elegido como el pivote cada vez, el peor escenario terminará ocurriendo una vez que el arreglo sea ordenado en orden descendente o ascendente. La recurrencia para el peor caso es la siguiente

T(n) = T(0) + T(n-1) + (n)que es equivalente a T(n) = T(n-1) + (n)

El mejor caso

El mejor caso ocurre siempre que el proceso de partición elige el elemento del medio como pivote. La recurrencia para el mejor caso es la siguiente

T(n) = 2T(n/2) + (n)

Caso medio

Hay que considerar cada permutación del array y calcular el tiempo que tarda cada permutación en realizar un análisis de casos. Por supuesto, este proceso puede ser bastante complicado, incluso para programadores experimentados. Dicho esto, tomar en consideración el caso en que la partición coloca O(n/9) junto con O(9n/10) elementos puede darle una estimación del caso promedio. La recurrencia de este caso es la siguiente

T(n) = T(n/9) + T(9n/10) + (n)

Preguntas comunes sobre Quick Sort

Aunque hay muchas preguntas sobre la ordenación rápida, las que se mencionan a continuación son probablemente las más comunes:

¿Es la ordenación rápida un algoritmo estable?

Bueno, la implementación por defecto de quick sort no tiene estabilidad. Dicho esto, es posible añadir estabilidad a los algoritmos de ordenación considerando el índice como parámetro de comparación.

¿Qué es la ordenación rápida en tres direcciones?

Cuando se trata de un algoritmo de ordenación rápida regular, elegimos un elemento para que actúe como pivote, creando una partición en el array. Después recurrimos a los subarreglos presentes en los lados derecho e izquierdo del pivote.

¿Es el Quick Sort un algoritmo in-place?

De acuerdo con la amplia definición de algoritmo in-place, quick sort califica efectivamente como este tipo de algoritmo de ordenación. Esto se debe a que utiliza espacio extra para almacenar las llamadas a funciones recursivas. Sin embargo, no manipula la entrada de ninguna manera.

Más rápido que la mayoría de los algoritmos de ordenación

Aunque no se puede negar que la complejidad de tiempo en el peor caso de quick sort es O(n2), más que heap sort, merge sort y otros numerosos algoritmos de ordenación, quick sort resulta ser increíblemente rápido. Una de las razones de esto es que puedes implementar eficientemente su bucle interno en varios tipos de datos y arquitecturas del mundo real.
Además, se puede implementar la ordenación rápida de varias maneras, simplemente cambiando la elección del pivote. Haciendo esto se minimiza la aparición del peor caso para cualquier tipo de datos. Dicho esto, los programadores generalmente prefieren utilizar la ordenación por fusión siempre que haya demasiados datos, especialmente si están dentro de un almacenamiento externo.

¿Qué pasa con el uso de la ordenación rápida en las listas enlazadas?

Cuando se trata de listas enlazadas, las cosas son bastante diferentes debido a las diferencias presentes en la asignación de memoria del array. Los nodos de las listas enlazadas son bastante diferentes a los arrays y a menudo no son adyacentes en la memoria. Además, las listas enlazadas permiten introducir elementos en el centro, algo que no es posible en los arrays. En estos escenarios, los programadores prefieren utilizar la ordenación por fusión, ya que resulta ser una opción más viable en comparación con la ordenación rápida.

Por qué los programadores prefieren la ordenación rápida a la ordenación de matrices

En su esencia, la ordenación rápida es una ordenación simple en el lugar, lo que significa que no necesita almacenamiento adicional. Por otro lado, la ordenación por fusión necesita O(N) de almacenamiento extra. Para aquellos que se lo pregunten, la N denota el tamaño del array, que puede ser increíblemente extenso. Desasignar y asignar el espacio extra necesario para la ordenación por fusión aumenta el tiempo de ejecución del algoritmo.

Una vez que comparamos la complejidad media, es fácil ver que la complejidad media de ambos tipos de ordenación es O(NlogN). Sin embargo, sus constantes tienden a diferir. Cuando se trata de matrices, la ordenación por fusión no tiene éxito porque utiliza el espacio de almacenamiento adicional O(N). Las implementaciones de ordenación rápida más prácticas utilizan la versión aleatoria. La complejidad temporal media de esta versión es O(nLogn). También hay que tener en cuenta que existe la posibilidad de un caso peor con la versión aleatoria. Sin embargo, no aparece en el caso de patrones específicos como el de un array ordenado.

El algoritmo de ordenación rápida es bastante amigable con la caché debido a su excelente localidad de referencia, particularmente cuando uno lo utiliza para arreglos. Además, la ordenación rápida también es recursiva en la cola, lo que significa que hay que realizar optimizaciones de llamadas en la cola.