¿Cómo aumentar el rendimiento de QuickSort?
El rendimiento de Quicksort se puede mejorar de varias maneras. En esta publicación, cubriremos algunos de ellos.
En la publicación anterior, hemos proporcionado una descripción general de los Algoritmo de clasificación rápida. Hemos visto que la complejidad de tiempo en el peor de los casos de Quicksort es O(n2), dónde n es el tamaño de la entrada. El peor de los casos ocurre cuando la lista ya está ordenada y cada llamada recursivo procesa una lista de tamaño uno menos que la lista anterior, lo que da como resultado O(n2) tiempo.
Además, la complejidad de tiempo en el mejor de los casos de Quicksort es O(n.log(n)). El mejor caso ocurre cuando el pivote divide la array en dos mitades casi iguales, y cada llamada recursivo procesa una lista de la mitad del tamaño.
El rendimiento de Quicksort se puede mejorar aún más de varias maneras:
1. Mejor selección de pivotes
En Quicksort, una de las operaciones críticas es elegir el pivote: el elemento alrededor del cual se divide la lista. Quicksort normalmente elige el elemento más a la izquierda o más a la derecha de la partición como elemento pivote. Esta selección provocará el peor de los casos en la entrada ordenada o casi ordenada. Podemos resolver el problema fácilmente eligiendo un índice aleatorio para el pivote (llamado Randomized Quicksort) o eligiendo la mediana del primer, medio y último elemento de la partición pivote (llamada selección de mediana de 3).
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
// Una rutina de partición aleatoria int randomizedPartition(int arr[], int start, int end) { // elige un índice aleatorio entre `start` y `end` int pivotIndex = rand() % (end - start + 1) + start; // intercambiar el elemento final con el elemento presente en el índice aleatorio swap(arr[pivotIndex], arr[end]); // llamar al procedimiento de partición return partition(arr, start, end); } // Quicksort usando la partición aleatoria void quicksort(int arr[] ,int start, int end) { // condición base if (start >= end) { return; } // reorganizar los elementos a través del pivote int pivot = randomizedPartition(arr, start, end); // recurre en un subarray que contiene elementos que son menores que el pivote quicksort(arr, start, pivot - 1); // se repite en el subarray que contiene elementos que son más que el pivote quicksort(arr, pivot + 1, end); } |
Se puede ver la implementación completa de la partición aleatoria. aquí.
2. Esquema de partición de Hoare
El esquema de partición de Hoare utiliza dos índices que comienzan en los extremos de la array que se está particionando, luego se mueven uno hacia el otro hasta que detectan una inversión: un par de elementos, uno mayor que el pivote, uno más pequeño, que están en el orden incorrecto en relación con El uno al otro. Luego se intercambian los elementos invertidos. Cuando los índices se encuentran, el algoritmo se detiene y devuelve el índice final.
El esquema de Hoare es más eficiente que la lógica de partición utilizada anteriormente (también llamada esquema de partición de Lomuto) porque hace tres veces menos intercambios en promedio. Crea particiones eficientes incluso cuando todos los valores son iguales. Se discute el esquema de partición de Hoare aquí.
3. Manejar elementos repetidos
Con un algoritmo de particionamiento como los descritos anteriormente (incluso con uno que elige buenos valores de pivote), Quicksort muestra un rendimiento deficiente en las entradas que contienen muchos elementos repetidos. El problema es visible cuando todos los elementos de entrada son iguales. Luego, en cada recursión, la partición izquierda está vacía (ningún valor de entrada es menor que el pivote), y la partición derecha solo ha disminuido en un elemento (se elimina el pivote). En consecuencia, el algoritmo necesita un tiempo cuadrático para ordenar una array de valores iguales.
Para resolver este problema (a veces llamado el Problema de la bandera nacional holandesa), se puede usar una rutina alternativa de partición de tiempo lineal que separa los valores en tres grupos: valores menores que el pivote, valores iguales al pivote y valores mayores que el pivote. Los valores iguales al pivote ya están ordenados, por lo que solo las particiones menor que y mayor que deben ordenarse recursivamentemente.
El mejor caso para el algoritmo ahora ocurre cuando todos los elementos son iguales (o se eligen de un pequeño conjunto de k << n elementos). El Quicksort modificado realizará como máximo dos llamadas recursivos en subarrays vacíos y, por lo tanto, terminará linealmente en todos los elementos idénticos. Este enfoque se discute aquí.
4. Uso de recursividad de cola
Para asegurarse como mucho O(log(n)) se usa el espacio, recurra primero al lado más pequeño de la partición, luego use una llamada de cola para volver al otro lado. Como tal, clasificamos con éxito la array de una manera que minimiza la profundidad recursivo.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
/* Reducir repetidamente la array desde el lado recurrente a través del control iterativo hasta que la array esté ordenada. En consecuencia, la array se ordena con éxito de una manera que maximiza el control iterativo, mientras minimiza la profundidad recursivo. */ void tailRecursiveQuicksort(int arr[], int start, int end) { while (start < end) { int pivot = partition(arr, start, end); // recurre en el subarray más pequeño if (pivot - start < end - pivot) { tailRecursiveQuicksort(arr, start, pivot - 1); start = pivot + 1; } else { tailRecursiveQuicksort(arr, pivot + 1, end); end = pivot - 1; } } } |
La implementación completa se puede ver aquí.
5. Híbrido con clasificación por inserción
Cuando el número total de elementos esté por debajo de cierto umbral (quizás diez elementos), cambie a un algoritmo de ordenación no recursivo como tipo de inserción que realiza menos intercambios, comparaciones u otras operaciones en arrays tan pequeños. Este enfoque se discute aquí.
En lugar de la optimización de "muchos tipos pequeños", la idea es detenerse cuando el número total de elementos es inferior a cierto umbral. k. Más tarde, cuando se haya procesado toda la array, cada elemento será como máximo k posiciones lejos de su posición ordenada final. Ahora, si realizamos una ordenación por inserción en él, tomará O(k.n) tiempo para terminar la ordenación, que es lineal como k es una constante
Referencias: https://en.wikipedia.org/wiki/Quicksort