Quicksort: elegir el pivote

Question

Al implementar Quicksort, una de las cosas que debe hacer es elegir un pivote. Pero cuando miro el pseudocódigo como el siguiente, no está claro cómo debería elegir el pivote. Primer elemento de la lista? ¿Algo más?

 function quicksort(array)
     var list less, greater
     if length(array) ≤ 1  
         return array  
     select and remove a pivot value pivot from array
     for each x in array
         if x ≤ pivot then append x to less
         else append x to greater
     return concatenate(quicksort(less), pivot, quicksort(greater))

¿Puede alguien ayudarme a comprender el concepto de elegir un pivote y si diferentes escenarios requieren o no diferentes estrategias?

Answer 1

Elegir un pivote aleatorio minimiza la posibilidad de que se encuentre con el rendimiento de O (n ² ) en el peor de los casos (elegir siempre el primero o el último causaría el peor de los casos en el caso de casi ordenados o casi al revés datos ordenados). Elegir el elemento del medio también sería aceptable en la mayoría de los casos.

Además, si está implementando esto usted mismo, hay versiones del algoritmo que funcionan en el lugar (es decir, sin crear dos listas nuevas y luego concatenarlas).

Answer 2

Depende de sus requisitos. Elegir un pivote al azar hace que sea más difícil crear un conjunto de datos que genere un rendimiento O (N ^ 2). 'Mediana de tres' (primero, último, medio) también es una forma de evitar problemas. Sin embargo, tenga cuidado con el rendimiento relativo de las comparaciones; Si sus comparaciones son costosas, Mo3 hace más comparaciones que elegir (un único valor de pivote) al azar. Los registros de la base de datos pueden ser costosos de comparar.

---

Actualización: extracción de comentarios en respuesta.

mdkess afirmó:

  

'Mediana de 3' NO es el primero, el último medio. Elija tres índices aleatorios y tome el valor medio de esto. El punto es asegurarse de que su elección de pivotes no sea determinista; si lo es, los datos del peor de los casos se pueden generar con bastante facilidad.

A lo que respondí:

• Análisis del algoritmo de búsqueda de Hoare con mediana de -Tres Particiones (1997) por P Kirschenhofer, H Prodinger, C Martínez apoya su afirmación (que 'mediana de tres' son tres elementos aleatorios).

• Hay un artículo que se describe en el portal .acm.org que trata sobre 'El peor caso de permutación para la mediana de tres Quicksort' de Hannu Erkiö, publicado en The Computer Journal, Vol. 27, No 3, 1984. [Actualización 2012-02-26: Obtuve el texto del artículo . La sección 2 'El algoritmo' comienza: ' Al usar la mediana de los elementos primero, medio y último de A [L: R], se pueden lograr particiones eficientes en partes de tamaños bastante iguales en la mayoría de las situaciones prácticas. 'Por lo tanto, está discutiendo el enfoque Mo3 primero-medio-último.]

• Otro artículo corto que es interesante es del MD McIlroy, " A Adversario asesino para Quicksort " , publicado en Software-Practice and Experience, vol. 29 (0), 1–4 (0 1999). Explica cómo hacer que casi cualquier Quicksort se comporte de forma cuadrática.

• AT & amp; T Bell Labs Tech Journal, octubre de 1984 "Teoría y práctica en la construcción de una rutina de trabajo". estados " Hoare sugirió particionar alrededor de la mediana de varias líneas seleccionadas al azar. Sedgewick [...] recomendó elegir la mediana del primer [...] último y medio [...] " ;. Esto indica que ambas técnicas para 'mediana de tres' son conocidas en la literatura. (Actualización 2014-11-23: el artículo parece estar disponible en IEEE Xplore o de Wiley - si es miembro o está dispuesto a pagar una tarifa).

• 'Ingeniería de una función de clasificación' por JL Bentley y MD McIlroy, publicado en Software Practice and Experience, Vol. 23 (11), noviembre de 1993, entra en una extensa discusión sobre los problemas, y eligieron un algoritmo de partición adaptativo basado en parte en el tamaño de los datos conjunto. Se discute mucho sobre las compensaciones para varios enfoques.

• Una búsqueda en Google de 'mediana de tres' funciona bastante bien para un mayor seguimiento.

Gracias por la información; Solo me había encontrado con la 'mediana de tres' determinista antes.

Answer 3

Je, acabo de enseñar esta clase.

Hay varias opciones.
Simple: elija el primer o el último elemento del rango. (malo en entrada parcialmente ordenada) Mejor: elija el elemento en el medio del rango. (mejor en entradas parcialmente ordenadas)

Sin embargo, elegir cualquier elemento arbitrario corre el riesgo de dividir mal la matriz de tamaño n en dos matrices de tamaño 1 y n-1. Si lo hace con la frecuencia suficiente, su clasificación rápida corre el riesgo de convertirse en O (n ^ 2).

Una mejora que he visto es elegir mediana (primero, último, medio); En el peor de los casos, todavía puede ir a O (n ^ 2), pero probabilísticamente, este es un caso raro.

Para la mayoría de los datos, elegir el primero o el último es suficiente. Pero, si descubre que a menudo se encuentra con el peor de los casos (entrada parcialmente ordenada), la primera opción sería elegir el valor central (que es un pivote estadísticamente bueno para datos parcialmente ordenados).

Si todavía tienes problemas, entonces ve por la ruta mediana.

Answer 4

Nunca elijas un pivote fijo: este puede ser atacado para explotar el tiempo de ejecución O (n ^ 2) en el peor de los casos de tu algoritmo, que es solo pedir problemas. El peor tiempo de ejecución de Quicksort ocurre cuando la partición da como resultado una matriz de 1 elemento y una matriz de elementos n-1. Suponga que elige el primer elemento como su partición. Si alguien alimenta una matriz a su algoritmo que está en orden decreciente, su primer pivote será el más grande, por lo que todo lo demás en la matriz se moverá a la izquierda. Luego, cuando repita, el primer elemento volverá a ser el más grande, por lo que una vez más, coloca todo a la izquierda, y así sucesivamente.

Una mejor técnica es el método de la mediana de 3, donde eliges tres elementos al azar y eliges el medio. Sabes que el elemento que elijas no será el primero ni el último, pero también, según el teorema del límite central, la distribución del elemento medio será normal, lo que significa que tenderás hacia el medio (y por lo tanto , n lg n tiempo).

Si absolutamente quiere garantizar el tiempo de ejecución de O (nlgn) para el algoritmo, el método de columnas de 5 para encontrar la mediana de una matriz se ejecuta en tiempo O (n), lo que significa que la ecuación de recurrencia para la clasificación rápida en el el peor de los casos será T (n) = O (n) (encuentra la mediana) + O (n) (partición) + 2T (n / 2) (recurrencia izquierda y derecha). Por el teorema maestro, esto es O (n lg n). Sin embargo, el factor constante será enorme, y si el rendimiento en el peor de los casos es su principal preocupación, utilice un tipo de fusión en su lugar, que es un poco más lento que el ordenamiento rápido en promedio y garantiza el tiempo O (nlgn) (y será mucho más rápido) que esta breve clasificación rápida).

Explicación del algoritmo de la mediana de las medianas

Answer 5

No intentes ser demasiado inteligente y combinar estrategias de pivote. Si combinó una mediana de 3 con un pivote aleatorio al elegir la mediana del primer, último y un índice aleatorio en el medio, entonces aún será vulnerable a muchas de las distribuciones que envían una mediana de 3 cuadrática (por lo que en realidad es peor que pivote aleatorio simple)

Por ejemplo, una distribución de órganos de tubos (1,2,3 ... N / 2..3,2,1) primero y último será 1 y el índice aleatorio será un número mayor que 1, tomando la mediana da 1 ( primero o último) y obtienes una partición extremadamente desequilibrada.

Answer 6

Para empezar, depende completamente de cómo se ordenan sus datos. Si cree que será pseudoaleatorio, entonces su mejor opción es elegir una selección aleatoria o elegir el medio.

Answer 7

Si está ordenando una colección accesible al azar (como una matriz), en general es mejor elegir el elemento medio físico. Con esto, si la matriz está ordenada (o casi ordenada), las dos particiones estarán casi iguales y obtendrá la mejor velocidad.

Si está ordenando algo con solo acceso lineal (como una lista vinculada), entonces es mejor elegir el primer elemento, porque es el elemento más rápido para acceder. Aquí, sin embargo, si la lista ya está ordenada, estás jodido: una partición siempre será nula y la otra lo tendrá todo, produciendo el peor momento.

Sin embargo, para una lista vinculada, elegir cualquier cosa además de la primera solo empeorará las cosas. Elige el elemento del medio en una lista de la lista, tendría que recorrerlo en cada paso de partición, agregando una operación O (N / 2) que se realiza logN veces haciendo el tiempo total O (1.5 N * log N) y eso es si sabemos cuánto tiempo dura la lista antes de comenzar. Por lo general, no lo hacemos, por lo que tendríamos que pasar por completo para contarlos, luego a mitad de camino para encontrar el medio y luego a través de un tercera vez para hacer la partición real: O (2.5N * log N)

Answer 8

Es más fácil dividir la clasificación rápida en tres secciones haciendo esto

1. Función de elemento de datos de intercambio o intercambio
2. La función de partición
3. Procesando las particiones

Es solo un poco más ineficaz que una función larga pero es mucho más fácil de entender.

El código sigue:

/* This selects what the data type in the array to be sorted is */

#define DATATYPE long

/* This is the swap function .. your job is to swap data in x & y .. how depends on
data type .. the example works for normal numerical data types .. like long I chose
above */

void swap (DATATYPE *x, DATATYPE *y){  
  DATATYPE Temp;

  Temp = *x;        // Hold current x value
  *x = *y;          // Transfer y to x
  *y = Temp;        // Set y to the held old x value
};


/* This is the partition code */

int partition (DATATYPE list[], int l, int h){

  int i;
  int p;          // pivot element index
  int firsthigh;  // divider position for pivot element

  // Random pivot example shown for median   p = (l+h)/2 would be used
  p = l + (short)(rand() % (int)(h - l + 1)); // Random partition point

  swap(&list[p], &list[h]);                   // Swap the values
  firsthigh = l;                                  // Hold first high value
  for (i = l; i < h; i++)
    if(list[i] < list[h]) {                 // Value at i is less than h
      swap(&list[i], &list[firsthigh]);   // So swap the value
      firsthigh++;                        // Incement first high
    }
  swap(&list[h], &list[firsthigh]);           // Swap h and first high values
  return(firsthigh);                          // Return first high
};



/* Finally the body sort */

void quicksort(DATATYPE list[], int l, int h){

  int p;                                      // index of partition 
  if ((h - l) > 0) {
    p = partition(list, l, h);              // Partition list 
    quicksort(list, l, p - 1);        // Sort lower partion
    quicksort(list, p + 1, h);              // Sort upper partition
  };
};

Answer 9

Idealmente, el pivote debería ser el valor medio en toda la matriz. Esto reducirá las posibilidades de obtener el peor rendimiento de caso.

Answer 10

La complejidad de la ordenación rápida varía mucho con la selección del valor de pivote. por ejemplo, si siempre elige el primer elemento como pivote, la complejidad del algoritmo se vuelve peor que O (n ^ 2). Aquí hay un método inteligente para elegir el elemento pivote: 1. Elija el primer, medio, último elemento de la matriz. 2. compare estos tres números y encuentre el número que sea mayor que uno y menor que otro, es decir, mediana. 3. Haga este elemento como elemento pivote.

elegir el pivote mediante este método divide la matriz en casi dos mitades y, por lo tanto, la complejidad se reduce a O (nlog (n)).

Answer 11

En promedio, la mediana de 3 es buena para n pequeño. La mediana de 5 es un poco mejor para n mayor. El ninther, que es la "mediana de tres medianas de tres". es aún mejor para n muy grande.

Cuanto más alto vaya con el muestreo, mejor obtendrá a medida que n aumente, pero la mejora se ralentiza drásticamente a medida que aumenta las muestras. E incurre en la sobrecarga de muestreo y clasificación de muestras.

Answer 12

Recomiendo usar el índice medio, ya que se puede calcular fácilmente.

Puede calcularlo redondeando (array.length / 2).

Answer 13

En una implementación verdaderamente optimizada, el método para elegir pivote debería depender del tamaño de la matriz: para una matriz grande, vale la pena pasar más tiempo eligiendo un buen pivote. Sin hacer un análisis completo, supongo que "medio de los elementos O (log (n))" es un buen comienzo, y tiene la ventaja adicional de que no requiere memoria adicional: al usar la llamada de cola en la partición más grande y la partición en el lugar, usamos la misma memoria adicional O (log (n)) en casi todas las etapas de el algoritmo.