Mejora en el algoritmo de clasificación rápida

Requisito previo: Algoritmo QuickSort

El algoritmo de clasificación rápida discutido en este artículo puede tomar tiempo O (N ² ) en el peor de los casos. Por lo tanto, se necesitan ciertas variaciones que puedan dividir eficientemente la array y reorganizar los elementos alrededor del pivote.

Partición de pivote único : en la partición de pivote único, la array A[] se puede dividir en {A[p], A[p + 1], A[p + 2], …, A[r]} en dos partes A[p …q] y A[q+1…r] tales que:

• Todos los elementos en la primera partición, A[p…q] son ​​menores o iguales al valor pivote A[q] .
• Todos los elementos de la segunda partición, A[q+1…r] son ​​mayores o iguales que el valor pivote A[q] .
• Después de eso, las dos particiones se tratan como arrays de entrada independientes y se alimentan al algoritmo de ordenación rápida .

Particionamiento de Lomuto : Este es el procedimiento de particionamiento más simple de implementar. Comenzando desde el elemento más a la izquierda y siguiendo el índice de elementos más pequeños (o iguales a) como i . Mientras se desplaza, si se encuentra un elemento más pequeño, intercambie el elemento actual con A[i] . De lo contrario, ignore el elemento actual. 

Se discute en detalle en este artículo.

Particionamiento de Hoare : funciona inicializando dos índices que comienzan en dos extremos, los dos índices se mueven uno hacia el otro hasta que se encuentra una inversión (un valor más pequeño en el lado izquierdo y un valor mayor en el lado derecho). Cuando se encuentra una inversión, se intercambian dos valores y se repite el proceso. El esquema de partición de Hoare es más eficiente que el esquema de partición de Lomuto porque hace tres veces menos intercambios en promedio y crea particiones eficientes incluso cuando todos los valores son iguales.

La comparación de las particiones de Lomuto y Hoare se discute en detalle aquí .

Pivote aleatorio :en los dos enfoques anteriores, la idea es tomar el primer o el último elemento de la array inexplorada y encontrar la posición correcta del elemento en la array considerándolo como el pivote. Si la array ya está ordenada en orden creciente o decreciente, y el primer elemento siempre se elige como pivote, entonces será siempre elelemento máximo o mínimoentre los elementos de la array no explorados. Reducirá el tamaño de la array no explorada solo en 1 y, por lo tanto, puede hacer que el algoritmo de clasificación rápida realice la complejidad de tiempo del peor de los casos de O(N ² ) .

En lugar de elegir el primer elemento como pivote cada vez, si elegimos un elemento aleatorio de la array inexplorada y lo intercambiamos con el primer elemento y luego realizamos el procedimiento de partición (cualquiera de los dos anteriores), entonces mejorará el esperado o complejidad de tiempo promedio a O(N*log N) . La complejidad del peor de los casos sigue siendo O(N ² ) . Sin embargo, cuando la array ya está ordenada, se evita el peor de los casos, pero se alcanza el peor de los casos cuando la array contiene muchos elementos repetidos. 

Para saber cómo un algoritmo aleatorio mejora la complejidad del tiempo de caso promedio, consulte este artículo .

Rendimiento con elementos repetidos : considere una array arr[] = [3, 3, 3, 3, 3, 3] , es decir, la array tiene todos (o muchos) elementos iguales. Al particionar esta array con el esquema de partición de un solo pivote, obtendremos dos particiones. La primera partición estará vacía, mientras que la segunda partición tendrá (N – 1) elementos . Además, cada invocación subsiguiente del procedimiento de partición reducirá el tamaño de entrada en solo uno. Dado que el procedimiento de partición tiene una complejidad O(N) , la complejidad temporal total será O(N ² ) . Este es el peor de los casos cuando la array de entrada tiene muchos elementos repetidos.

Para reducir los peores escenarios cuando los elementos repetidos se encuentran en grandes cantidades, en lugar de un esquema de partición de un solo pivote, podemos implementar un esquema de partición de tres vías.

Particionamiento de tres vías : para ordenar de manera eficiente una array que tiene una gran cantidad de claves repetidas, podemos colocar las claves en la posición correcta cuando las encontramos por primera vez. Entonces, la partición de tres vías de la array consta de las siguientes tres particiones:

• La partición más a la izquierda contiene elementos que son estrictamente menores que el pivote.
• La partición central contiene todos los elementos que son iguales al pivote.
• La partición más a la derecha contiene todos los elementos que son estrictamente mayores que el pivote.

Algoritmo de clasificación de la bandera nacional holandesa (DNF) :puede categorizar todos los números de una array en tres grupos con respecto a un pivote dado:

• El grupo Menor contiene todos los elementos que son estrictamente menores que el pivote.
• El grupo Igual contiene todos los elementos que son iguales al pivote.
• el mayorEl grupo contiene todos los elementos estrictamente mayores que el pivote.

Para resolver el problema de DNF, elija el primer elemento como pivote y escanee la array de izquierda a derecha. A medida que revisamos cada elemento, lo movemos a su grupo correcto, a saber, Menor , Igual y Mayor .

Para conocer la implementación del algoritmo de clasificación DNF, consulte este artículo .

Partición de 3 vías optimizada de Bentley-McIlroy : este algoritmo es un esquema de partición basado en iteraciones . Todos los elementos de la array están inexplorados inicialmente. Comience a explorar los elementos de la array desde las direcciones izquierda y derecha. Después de cada iteración, se puede visualizar que la array es una composición de cinco regiones:

• Los dos extremos extremos son regiones que tienen elementos iguales al valor del pivote.
• La región inexplorada permanece en el centro y su tamaño sigue reduciéndose con cada iteración.
• En el lado izquierdo de la región inexplorada hay elementos menores que el valor pivote.
• En el lado derecho de la región inexplorada hay elementos mayores que el valor pivote.

A medida que continúa el procedimiento de iteración, la región inexplorada de la array sigue disminuyendo y, finalmente, la array no tendrá ningún elemento inexplorado restante. 

Ahora, dado que los elementos iguales al elemento pivote son mayores que los elementos de la región menor y menores que los elementos de la región mayor, es necesario moverlos al centro entre la región menor y la mayor. Se llevan al centro mediante el intercambio con elementos de regiones menores y mayores.

Finalmente, el problema se reduce a ordenar los elementos en una región menor y mayor utilizando el mismo enfoque nuevamente hasta que se ordena toda la array.

Análisis del particionamiento de tres vías : en general, el algoritmo de clasificación rápida tiene una complejidad de tiempo de caso promedio de O(N*log(N)) y una complejidad de tiempo de caso peor de O(N ² ) . Con una gran cantidad de claves duplicadas, siempre obtenemos el peor rendimiento posible con la implementación trivial de Quick Sort.

Sin embargo, el uso de particiones de tres vías reduce el impacto de numerosas claves duplicadas. De hecho, una array con todos los elementos se ordena en tiempo O(N ² ) en partición de un solo pivote mientras que se ordena en complejidad de tiempo O(N) (lineal) en partición de tres vías. Por lo tanto, lo que solía ser el peor de los casos se convierte en el mejor de los casos para la partición de tres vías.