algorithm - complexity - Estabilidad del enfoque de partición quicksort

quicksort javascript

Question

El resultado del siguiente algoritmo de partición Quicksort es una clasificación estable (es decir, mantiene la posición relativa de los elementos con valores iguales):

  partition(A,p,r)
  {
     x=A[r];
     i=p-1;
     for j=p to r-1
       if(A[j]<=x)
          i++;
          exchange(A[i],A[j])

       exchang(A[i+1],A[r]); 
     return i+1;
   }

Answer 1

Cualquier orden se puede convertir en una ordenación estable si está dispuesto a agregar una segunda clave. La segunda clave debe ser algo que indique el orden original, como un número de secuencia. En su función de comparación, si las primeras teclas son iguales, use la segunda tecla.

Answer 2

De Wikipedia:

Quicksort es una ordenación de comparación y, en implementaciones eficientes, no es una ordenación estable.

Answer 3

Hay un caso en el que su algoritmo de partición hará un intercambio que cambiará el orden de los valores iguales. Aquí hay una imagen que ayuda a demostrar cómo funciona su algoritmo de partición en el lugar:

Marchamos a través de cada valor con el índice j, y si el valor que vemos es menor que el valor de la partición, lo agregamos al subarreglo gris claro intercambiándolo con el elemento que está inmediatamente a la derecha del subarray gris claro . El subarreglo gris claro contiene todos los elementos que son <= el valor de la partición. Ahora veamos, digamos, la etapa (c) y consideremos el caso en el que tres 9 están al principio de la zona blanca, seguido de un 1. Es decir, estamos por comprobar si los 9 son <= el valor de partición . Miramos los primeros 9 y vemos que no es <= 4, por lo que lo dejamos en su lugar y avanzamos j. Miramos los siguientes 9 y vemos que no es <= 4, por lo que también lo dejamos en su lugar y marchamos j hacia adelante. También dejamos el tercer 9 en su lugar. Ahora miramos el 1 y vemos que es menor que la partición, así que lo intercambiamos con el primer 9. Luego, para terminar el algoritmo, intercambiamos el valor de la partición con el valor de i + 1, que es el segundo 9. Ahora hemos completado el algoritmo de partición, y el 9 que originalmente era tercero ahora es el primero.

Answer 4

La clasificación rápida no es estable. Aquí es el caso cuando no es estable.

5 5 4 8

tomando 1st 5 como pivote, tendremos seguimiento después de 1st pass-

4 5 5 8

Como se puede ver, el orden de 5 ha sido cambiado. Ahora, si continuamos haciendo la clasificación, cambiaremos el orden de 5 en la matriz ordenada.

Answer 5

Si necesita una clasificación O (n * log (n) estable, use mergesort . (Por cierto, la mejor manera de hacer que el orden sea estable es elegir una mediana de valores aleatorios como pivote. Sin embargo, esto no es estable para todos los elementos equivalentes).

Answer 6

Su código parece sospechosamente similar a la función de partición de muestra dada en wikipedia que no es estable, por lo que su función probablemente no sea estable. Como mínimo, debe asegurarse de que su punto de pivote r apunte a la última posición en la matriz de valores igual a A [r].

Puede hacer que el orden sea estable (no estoy de acuerdo con Matthew Jones) pero no en su forma predeterminada y más rápida (jeje).

Martin (ver los comentarios) tiene razón en que un pedido rápido en una lista vinculada comienza con el primer elemento como pivote y agrega valores al final de las sublistas superiores e inferiores a medida que avanza por la matriz. Sin embargo, se supone que quicksort funciona en una matriz simple en lugar de en una lista vinculada. Una de las ventajas de quicksort es su bajo espacio de memoria (porque todo sucede en su lugar). Si está utilizando una lista vinculada, ya está incurriendo en una sobrecarga de memoria para todos los punteros a los siguientes valores, etc., y los está intercambiando en lugar de los valores.

Answer 7

Una clasificación es estable cuando el orden original de elementos similares no cambia. Su algoritmo no es estable ya que intercambia elementos iguales.

Si no fuera así, entonces no sería estable:

( 1, 5, 2, 5, 3 )

Tienes dos elementos con la clave de clasificación "5". Si compara el elemento # 2 (5) y # 5 (3) por alguna razón, entonces el 5 se intercambiaría por 3, lo que violaría el contrato de una forma estable. Esto significa que elegir con cuidado el elemento de pivote no ayuda, también debe asegurarse de que la copia de elementos entre las particiones nunca cambie el orden original.

Answer 8

Una forma de resolver este problema es no tomar el último elemento de la matriz como clave. La ordenación rápida es un algoritmo aleatorio.

Su rendimiento depende en gran medida de la selección de la clave. Aunque el algoritmo def dice que debemos tomar el último o primer elemento como clave, en realidad podemos seleccionar cualquier elemento como clave.

Así que probé el enfoque de mediana de 3, que dice tomar primero, medio y último elemento de la matriz. Los clasifica y luego usa la posición media como una llave.

Entonces, por ejemplo, mi matriz es {9,6,3,10,15} . Entonces, al clasificar el primer, el medio y el último elemento será {3,6,9,10,15} . Ahora usa 9 como clave. Así que mover la llave al final será {3,6,15,10,9} .

Todo lo que debemos tener en cuenta es qué sucede si 9 aparece más de una vez. Esa es la clave en sí misma viene más de una vez.

En tales casos, después de seleccionar la clave como índice medio, debemos pasar por los elementos entre la clave al extremo derecho y, si se encuentra algún elemento, la misma clave, es decir, si se encuentra 9 entre la posición central y el final, haga que 9 sea la clave.

Ahora en la región de los elementos mayores que 9, es decir, el bucle de j si se encuentra 9, intercambie con la región de los elementos menos que la región de i. Su matriz será estable ordenada.