algorithm - Quicksort: Elegir el pivote

quicksort algorithm

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))

¿Alguien puede ayudarme a comprender el concepto de elegir un pivote y si diferentes escenarios requieren diferentes estrategias?

Answer 1

Depende de tus requisitos. Elegir un pivote al azar hace que sea más difícil crear un conjunto de datos que genere O (N ^ 2) rendimiento. ''Mediana de tres'' (primero, último, medio) es también una forma de evitar problemas. Sin embargo, tenga cuidado con el rendimiento relativo de las comparaciones; si sus comparaciones son costosas, entonces 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: Tirar comentarios en respuesta.

mdkess afirmó:

''Mediana de 3'' NO es la primera en el medio. Elija tres índices aleatorios y tome el valor medio de esto. El objetivo es asegurarse de que su elección de pivotes no sea determinista; si lo es, los datos del caso más desfavorable pueden generarse fácilmente.

A lo que respondí:

• Análisis del algoritmo de búsqueda de Hoare con partición de mediana de tres (1997) por P Kirschenhofer, H Prodinger, C Martínez respalda su afirmación (que la ''mediana de tres'' es tres ítems aleatorios).

• Hay un artículo descrito en portal.acm.org que trata sobre "La peor permutación de casos para Mediana-de-tres Quicksort" por Hannu Erkiö, publicado en The Computer Journal, Vol 27, No 3, 1984. [Actualización 2012-02- 26: Tengo el texto para el article . 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 primer enfoque de Mo3, el medio y el último.]

• Otro breve artículo que es interesante es el de MD McIlroy, "A Killer Adversary for 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 & T Bell Labs Tech Journal, octubre de 1984 "Teoría y práctica en la construcción de una rutina de clasificación de trabajo" afirma "Hoare sugirió la partición en torno a la mediana de varias líneas seleccionadas al azar. [...] Sedgewick recomendó elegir la mediana del primero [. ..] último [...] y medio ". Esto indica que ambas técnicas para ''mediana de tres'' son conocidas en la literatura. (Actualización del 2014-11-23: el artículo parece estar disponible en IEEE Xplore o en Wiley , si tiene membresía o está dispuesto a pagar una tarifa).

• ''Engineering a Sort Function'' de JL Bentley y MD McIlroy, publicado en Software Practice and Experience, Vol 23 (11), noviembre de 1993, entra en una extensa discusión de los problemas, y ellos eligieron un algoritmo de partición adaptativo basado en parte en el tamaño del conjunto de datos. Existe una gran cantidad de discusiones sobre 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 antes con la ''mediana de tres'' determinista.

Answer 2

Depende enteramente de cómo se ordenan sus datos para comenzar. Si crees que será pseudoaleatorio, la mejor opción es elegir una selección al azar o elegir la del medio.

Answer 3

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

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

Answer 4

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

Mientras más alto va con el muestreo, mejor se obtiene cuando n aumenta, pero la mejora se ralentiza dramáticamente a medida que aumenta las muestras. Y incurre en los gastos generales de muestreo y clasificación de muestras.

Answer 5

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

Answer 6

Es más fácil dividir el servicio rápido en tres secciones haciendo esto

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

Es solo un poco más ineficiente 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 7

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

Answer 8

Je, acabo de enseñar esta clase.

Hay varias opciones.
Simple: elija el primer o el último elemento del rango. (Mal en la entrada parcialmente clasificada) Mejor: Elija el elemento en el medio del rango. (mejor en entrada parcialmente clasificada)

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

Una mejora que he visto es escoger 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 encuentra que se encuentra con los peores escenarios a menudo (entrada parcialmente ordenada), la primera opción sería elegir el valor central (que es un pivote estadísticamente bueno para los datos parcialmente ordenados).

Si aún te encuentras con problemas, entonces sigue la ruta de la mediana.

Answer 9

La complejidad de la clasificació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 tan mala como O (n ^ 2). aquí hay un método inteligente para elegir el elemento pivote: 1. elija el primer, medio y último elemento de la matriz. 2. compara estos tres números y encuentra el número que es mayor que uno y más pequeño que el otro, es decir, la mediana. 3. hacer este elemento como elemento pivote.

la elección del pivote por este método divide la matriz en casi dos medios y, por lo tanto, la complejidad se reduce a O (nlog (n)).

Answer 10

No intentes ponerte demasiado listo y combinar estrategias pivotantes. Si combina la mediana de 3 con pivote aleatorio eligiendo la mediana del primer, último y un índice aleatorio en el medio, entonces seguirá siendo vulnerable a muchas de las distribuciones que envían una mediana de 3 cuadráticos (por lo que es peor que pivote aleatorio simple)

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

Answer 11

Nunca elija un pivote fijo; puede atacarlo para aprovechar el tiempo de ejecución O (n ^ 2) del caso más desfavorable de su algoritmo, lo cual no hace más que plantear problemas. El peor tiempo de ejecución de Quicksort ocurre al particionar los resultados en una matriz de 1 elemento y una matriz de n-1 elementos. Supongamos 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 de la misma. Luego, cuando repites, el primer elemento volverá a ser el más grande, así que una vez más, colocas 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, por el teorema del límite central, la distribución del elemento medio será normal, lo que significa que tenderás hacia el centro (y por lo tanto , n lg n tiempo).

Si desea 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 conexión rápida en el peor de los casos ser T (n) = O (n) (encontrar la mediana) + O (n) (partición) + 2T (n / 2) (recursivo a la izquierda y a la derecha.) Según el teorema maestro, esto es O (n lg n) . Sin embargo, el factor constante será enorme, y si el peor de los casos es su principal preocupación, use una combinación de fusión, que es solo un poco más lenta que la oferta promedio y garantiza el tiempo O (nlgn) (y será mucho más rápido) que este medio rápido cojo).

Explicación de la mediana del algoritmo de las medianas

Answer 12

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

Puede calcularlo redondeando (array.length / 2).

Answer 13

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

Si está ordenando algo solo con acceso lineal (como una lista enlazada), 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 equivocado: una partición siempre será nula y la otra tendrá todo, produciendo el peor momento.

Sin embargo, para una lista enlazada, elegir cualquier cosa además de la primera, solo empeorará las cosas. Selecciona el elemento del medio en una lista listada, debe recorrerlo en cada paso de la partición - agregando una operación O (N / 2) que se realiza logN veces haciendo un tiempo total O (1.5 N * log N) y eso es si sabemos cuánto tiempo es la lista antes de comenzar, generalmente no, así que tendríamos que pasar todo el camino para contarlas, luego dar un paso hacia la mitad para encontrar el centro y luego tercera vez para hacer la partición real: O (2.5N * log N)