algorithm - rapido - estabilidad del algoritmo de orden rápida

ordenamiento metodo de insercion

Question

Quicksort no es estable, ya que intercambia elementos no adyacentes.

Por favor, ayúdame a entender esta declaración.

Sé cómo funciona la partición y qué es la estabilidad. Pero no puedo entender qué hace que lo anterior sea la razón para que esto no sea estable. Entonces creo que se puede decir lo mismo para la clasificación de fusión, aunque se cita como un algoritmo estable.

Answer 1

Considere la siguiente matriz de pares:

{(4,''first'');(2,'''');(1,'''');(4,''second'');(3,'''')}

Considera 3 como pivote. Durante una ejecución de ordenación rápida, la matriz experimenta los siguientes cambios:

1. {(4,''first'');(2,'''');(1,'''');(4,''second'');(3,'''')}
2. {(2,'''');(4,''first'');(1,'''');(4,''second'');(3,'''')}
3. {(2,'''');(1,'''');(4,''first'');(4,''second'');(3,'''')}
4. {(2,'''');(1,'''');(3,'''');(4,''second'');(4,''first'')}
5. {(1,'''');(2,'''');(3,'''');(4,''second'');(4,''first'')}

Claramente de lo anterior, se cambia el orden relativo. Esta es la razón por la que se dice que la clasificación rápida "no garantiza la estabilidad".

Answer 2

Considere lo que sucede durante la partición para la siguiente matriz de pares, donde el comparador usa el entero (solo). La cadena está justo allí, de modo que tenemos dos elementos que se comparan como si fueran iguales, pero que en realidad son distinguibles.

(4, "first"), (2, ""), (3, ""), (4, "second"), (1, "")

Por definición, una clasificación es estable si, después de la clasificación, los dos elementos que se comparan como si fueran iguales (los dos 4 s) aparecen en el mismo orden posterior a como lo hicieron antes.

Supongamos que elegimos 3 como el pivote. Los dos 4 elementos terminarán después de él y el 1 y el 2 antes de él (hay algo más que eso, he ignorado mover el pivote ya que está en la posición correcta, pero usted dice que entiende la partición).

En general, las acciones rápidas no ofrecen ninguna garantía en particular donde, después de la partición, los dos 4 s serán, y creo que la mayoría de las implementaciones los revertirán. Por ejemplo, si usamos el algoritmo de partición clásico de Hoare , la matriz se divide de la siguiente manera:

(1, ""), (2, ""), (3, ""), (4, "second"), (4, "first")

Lo que viola la estabilidad de la clasificación.

Dado que cada partición no es estable, es probable que la clasificación general no lo sea.

Como lo señala Steve314 en un comentario, la clasificación de fusión es estable siempre que al fusionar, si encuentra elementos iguales, siempre emita primero el que provino de la "parte inferior" de las dos mitades en las que se está fusionando. Es decir, cada combinación tiene que verse así, donde la "izquierda" es el lado que viene de abajo hacia abajo en la matriz original.

while (left not empty and right not empty):
    if first_item_on_left <= first_item_on_right:
       move one item from left to output
    else:
       move one item from right to output
move everything from left to output
move everything from right to output

Si <= were < entonces la fusión no sería estable.

Answer 3

Se dice que una clasificación es estable si se conserva el orden de los elementos equivalentes. La estabilidad de quicksort depende de la estrategia de partición. "Quicksort no es estable ya que intercambia elementos no adyacentes". Esta declaración se basa en el requisito previo de que se utilice la partición Hoare. Esta es una demo de Hoare Partioning de Berkeley CS61b, Hoare Partitioning

Debe saber lo que significa "intercambia elementos no adyacentes".

Answer 4

Será como si un usuario tuviera una matriz ordenada, y la ordenara por otra columna, ¿el algoritmo de clasificación siempre conserva el orden relativo de los elementos que difieren de la clave de clasificación anterior pero tienen el mismo valor en la nueva clave de clasificación? Por lo tanto, en un algoritmo de clasificación que siempre conserva el orden de los elementos (que no difieren en la nueva clave de clasificación) se denomina "clasificación estable".