Visión general de los algoritmos de ordenamiento Quicksort
Resumen de los algoritmos de ordenamiento Quicksort
Descubre uno de los algoritmos de ordenamiento más eficientes
Introducción
Quicksort es probablemente el algoritmo de ordenamiento más popular. En muchos experimentos, se ha demostrado que en promedio tiene un mejor rendimiento que otros métodos de ordenamiento como merge sort o heap sort.
Quicksort se basa en la idea de dividir recursivamente un arreglo en dos partes: la primera que contiene todos los elementos que son menores que un elemento pivote y la segunda que consiste en elementos mayores. Este procedimiento se llama partición. La función de partición se llama recursivamente en ambas partes divididas del arreglo hasta que solo quede un elemento por particionar.
Partición
Inicialmente, es necesario elegir un elemento pivote. Puede ser cualquier elemento del arreglo. En nuestro ejemplo, elegiremos el último elemento del arreglo. Luego, recorreremos un bucle donde en cada iteración compararemos el elemento actual con el pivote. Si el elemento es menor o igual al pivote, se mantendrá en la parte izquierda del arreglo. De lo contrario, el elemento se moverá a la parte derecha.
Primero, inicializamos dos punteros: i y j. El índice j apunta al primer elemento mientras que i apunta a su valor precedente j – 1. Con las variables introducidas i y j, se cumplen las siguientes invariantes a lo largo del bucle:
- Cómo evaluar representaciones
- Prácticas recomendadas de trazado distribuido
- Tim Davis, Co-Fundador y Presidente de Modular – Serie de Ent...
- Los elementos con índices [izquierda, i] son menores o iguales al pivote.
- Los elementos con índices [i + 1, j) son mayores que el pivote.
Al final del bucle, j será igual a la derecha y el índice i dividirá el arreglo en dos partes. Debido a las invariantes verdaderas, nuestro arreglo estará correctamente particionado.
En cada iteración, j se incrementa en 1, por lo que siempre apunta al elemento actual. Luego, se compara el elemento actual array[j] con el pivote. Si el elemento es menor o igual al pivote, se intercambia con el elemento en la posición i + 1. De acuerdo con la invariante mencionada anteriormente, siempre sabemos que array[i + 1] > pivote. Como resultado, el elemento que es menor o igual al pivote se intercambia en la dirección izquierda con un elemento que es mayor que el pivote. Al hacer este intercambio, nuestra invariante se viola. Para que la invariante sea correcta después de esto, se incrementa i en 1.
Si array[j] > pivote, entonces la invariante sigue siendo correcta y simplemente pasamos a la siguiente iteración (i no cambia su valor).
Es fácil darse cuenta de que después de todas las iteraciones, el arreglo estará correctamente particionado. La lógica descrita se muestra en el fragmento de código a continuación. Observa que se devuelve el índice del elemento pivote.
Función de partición
Ordenamiento
El algoritmo de ordenamiento procede recursivamente. En primer lugar, se particiona el arreglo en dos partes, según la sección anterior. Para cada una de ellas, se invoca recursivamente el procedimiento de partición nuevamente hasta que solo quede 1 elemento por particionar.
A continuación se muestra la función para este algoritmo.
Función de Quicksort
Complejidad
Dado que la prueba asintótica precisa para quicksort incluye demasiados detalles y es relativamente compleja, no me gustaría profundizar en todos los aspectos, sino proporcionar una prueba informal.
Durante cada llamada a la partición, pasamos linealmente por todos los elementos del arreglo, lo que resulta en una complejidad O(K) donde K es el tamaño del arreglo. Supongamos que después de cada procedimiento de partición, el elemento pivote separa el arreglo en dos mitades iguales, por lo que llamamos recursivamente a la función quicksort para ambas hasta que solo quede 1 elemento por ordenar. Esto resulta en la siguiente estructura de llamadas a funciones que se ve igual para merge sort.
La única diferencia es que en lugar de la función de combinación, llamamos a la función de partición, pero ambas tienen la misma complejidad temporal O(K). Dado que la estructura jerárquica también es la misma, podemos resumir que la complejidad temporal para el ordenamiento rápido es O(N * logN). La prueba asintótica para el ordenamiento por mezcla se puede encontrar aquí.
Algoritmos de Ordenamiento, Parte 1: Ordenamiento por Mezcla
Cuando se trata de ordenar, el ordenamiento por mezcla es uno de los algoritmos más populares. Se basa en el famoso…
VoAGI.com
En la prueba anterior, asumimos que el arreglo siempre se divide en dos mitades iguales, lo cual, obviamente, no siempre es cierto. Supongamos que el procedimiento de partición siempre separa solo un elemento de los demás. Esto resultará en tamaños de arreglo de N – 1, N – 2, N – 3, …, 1 en todas las iteraciones en las que se invoque el procedimiento de partición. Calculemos la complejidad temporal total para este escenario utilizando la fórmula de sumatoria para la progresión aritmética.
T(N) = O(N) + O(N – 1) + O(N – 2) + O(N – 3) + … + O(1) = O(N * (N + 1) / 2) = O(N²)
Como resultado, obtenemos una complejidad temporal cuadrática. Este es el peor caso posible para el ordenamiento rápido. A pesar de esto, la probabilidad de este escenario es muy pequeña.
En promedio, el ordenamiento rápido funciona en O(N * logN) tiempo y supera a otros algoritmos de ordenamiento.
Imagina que desarrollas un sistema que utiliza un algoritmo de ordenamiento rápido internamente. No sería una buena idea elegir siempre un elemento pivote, según el mismo principio (en nuestro ejemplo, estábamos eligiendo constantemente el elemento final del arreglo). Si alguien descubre la estrategia de elección de un elemento pivote en el sistema, entonces esta persona puede ingresar expresamente arreglos que resulten en los peores escenarios de partición y, como consecuencia, en una complejidad temporal O(N²). Esto podría disminuir significativamente la eficiencia del sistema. Por eso siempre es mejor elegir pivotes de diferentes maneras en cada iteración. Una de las formas más populares de hacerlo es elegir un pivote al azar.
Conclusión
Hemos estudiado el ordenamiento rápido, un algoritmo conocido para el ordenamiento. A pesar de tener una complejidad cuadrática en el peor escenario, sigue siendo generalmente más eficiente en la práctica, en comparación con otros algoritmos como el ordenamiento por mezcla o el ordenamiento por montón, especialmente en el caso de arreglos grandes.
Todas las imágenes, a menos que se indique lo contrario, son del autor
