algorithms - quicksort pseudocode
mediana de la estrategia de tres valores (7)
¿Cuál es la mediana de la estrategia de tres para seleccionar el valor de pivote en ordenamiento rápido?
Lo estoy leyendo en la web, pero no pude averiguar qué es exactamente? Y también cómo es mejor que la clasificación rápida aleatoria.
Creo que reorganizar los valores en la matriz no es necesario solo para tres valores. Simplemente compáralos todos restando; entonces usted puede decidir cuál es el valor de la mediana:
// javascript:
var median_of_3 = function(a, b, c) {
return ((a-b)*(b-c) > -1 ? b : ((a-b)*(a-c) < 1 ? a : c));
}
El quicksort de common / vanilla selecciona como pivote el elemento más a la derecha. Esto tiene la consecuencia de que muestra un rendimiento patológico O (N²) para varios casos. En particular las colecciones ordenadas y las ordenadas inversamente. En ambos casos, el elemento más a la derecha es el peor elemento posible para seleccionar como un pivote. El pivote es idealmente pensado para mí en el medio de la partición. Se supone que la partición divide los datos con el pivote en dos secciones, una baja y una alta. La sección baja es más baja que el pivote, mientras que la sección alta es más alta.
Mediana de tres selección de pivote:
- Seleccione el elemento más a la izquierda, medio y más a la derecha
- Ordénelos a la partición izquierda, pivote y partición derecha. Use el pivote de la misma manera que lo hace el pedido rápido regular.
Las patologías comunes O (N²) de las entradas clasificadas / invertidas se mitigan con esto. Todavía es fácil crear entradas patológicas para la mediana de tres. Pero es un uso construido y malicioso. No es un pedido natural.
Pivote al azar :
- Seleccione un pivote aleatorio. Utilice esto como un elemento de pivote regular.
Si es aleatorio, esto no muestra un comportamiento patológico de O (N²). El pivote aleatorio suele ser computacionalmente muy intensivo para una clasificación genérica y, como tal, no deseable. Y si no es aleatorio (es decir, srand (0);, rand (), predecible y vulnerable a la misma explotación de O (N²) que la anterior.
Tenga en cuenta que el pivote aleatorio no se beneficia de seleccionar más de un elemento. Principalmente porque el efecto de la mediana ya es intrínseco, y un valor aleatorio es más intensivo computacionalmente que el ordenamiento de dos elementos.
Esta estrategia consiste en elegir tres números de forma determinista o aleatoria y luego usar su mediana como pivote.
Esto sería mejor porque reduce la probabilidad de encontrar pivotes "malos".
La mediana de tres hace que mire los elementos primero, medio y último de la matriz, y elija la mediana de esos tres elementos como pivote.
Para obtener el "efecto completo" de la mediana de tres, también es importante clasificar esos tres elementos, no solo usar la mediana como pivote, esto no afecta lo que se eligió como pivote en la iteración actual, sino que puede / afectará lo que se usa como pivote en la próxima llamada recursiva, lo que ayuda a limitar el mal comportamiento de algunos pedidos iniciales (uno que resulta ser particularmente malo en muchos casos es una matriz que está ordenada, excepto por tener el elemento más pequeño en el extremo superior de la matriz (o el elemento más grande en el extremo inferior). Por ejemplo:
En comparación con elegir el pivote al azar:
- Asegura que un caso común (datos ordenados completamente) permanezca óptimo.
- Es más difícil manipularlo para dar el peor de los casos.
- Un PRNG es a menudo relativamente lento.
Ese segundo punto probablemente conlleva un poco más de explicación. Si usó el generador de números aleatorios obvios ( rand() ), es bastante fácil (para muchos casos, de todos modos) que alguien organice los elementos para que elija continuamente los pivotes pobres. Esto puede ser una preocupación seria para algo como un servidor web que puede estar clasificando los datos que ha sido ingresado por un posible atacante, que podría organizar un ataque DoS haciendo que su servidor pierda mucho tiempo clasificando los datos. En un caso como este, podría usar una semilla verdaderamente aleatoria, o podría incluir su propio PRNG en lugar de usar rand (), o usar la Mediana de tres, que también tiene las otras ventajas mencionadas.
Por otro lado, si utiliza un generador suficientemente aleatorio (por ejemplo, un generador de hardware o un cifrado en el modo de contador), probablemente sea más difícil forzar un caso malo de lo que es para una mediana de tres selecciones. Al mismo tiempo, alcanzar ese nivel de aleatoriedad generalmente tiene un poco de sobrecarga propia, por lo que, a menos que realmente espere ser atacado en este caso, probablemente no valga la pena (y si lo hace, probablemente valga la pena al menos considerar un alternativa que garantiza O (N log N) en el peor de los casos, como una ordenación por combinación o ordenación por almacenamiento dinámico.
Piensa simple ... Ejemplo de Python ....
def bigger(a,b): #Find the bigger of two numbers ... if a > b: return a else: return b def biggest(a,b,c): #Find the biggest of three numbers ... return bigger(a,bigger(b,c)) def median(a,b,c): #Just dance! x = biggest(a,b,c) if x == a: return bigger(b,c) if x == b: return bigger(a,c) else: return bigger(a,b)
Podemos entender la estrategia de la mediana de tres con un ejemplo, supongamos que nos dan una matriz:
[8, 2, 4, 5, 7, 1]
Así que el elemento más a la izquierda es 8 , y el elemento más a la derecha es 1 . El elemento central es 4 , ya que para cualquier matriz de longitud 2k , elegiremos el elemento k th.
Y luego ordenamos estos tres elementos en orden ascendente o descendente, lo que nos da:
[1, 4, 8]
Así, la mediana es 4 . Y usamos 4 como nuestro pivote.
En el lado de la implementación, podemos tener:
// javascript
function findMedianOfThree(array) {
var len = array.length;
var firstElement = array[0];
var lastElement = array[len-1];
var middleIndex = len%2 ? (len-1)/2 : (len/2)-1;
var middleElement = array[middleIndex];
var sortedArray = [firstElement, lastElement, middleElement].sort(function(a, b) {
return a < b; //descending order in this case
});
return sortedArray[1];
}
Otra forma de implementarlo está inspirada en @kwrl, y me gustaría explicarlo un poco más claro:
// javascript
function findMedian(first, second, third) {
if ((second - first) * (third - first) < 0) {
return first;
}else if ((first - second) * (third - second) < 0) {
return second;
}else if ((first - third)*(second - third) < 0) {
return third;
}
}
function findMedianOfThree(array) {
var len = array.length;
var firstElement = array[0];
var lastElement = array[len-1];
var middleIndex = len%2 ? (len-1)/2 : (len/2)-1;
var middleElement = array[middleIndex];
var medianValue = findMedian(firstElement, lastElement, middleElement);
return medianValue;
}
Considere la función findMedian , el primer elemento será devuelto solo cuando second Element > first Element > third Element y third Element > first Element > second Element , y en ambos casos: (second - first) * (third - first) < 0 , el El mismo razonamiento se aplica a los dos casos restantes.
La ventaja de usar la segunda implementación es que podría tener un mejor tiempo de ejecución.
Una implementación de Median of Three que he encontrado funciona bien en mis clases rápidas.
(Python)
# Get the median of three of the array, changing the array as you do.
# arr = Data Structure (List)
# left = Left most index into list to find MOT on.
# right = Right most index into list to find MOT on
def MedianOfThree(arr, left, right):
mid = (left + right)/2
if arr[right] < arr[left]:
Swap(arr, left, right)
if arr[mid] < arr[left]:
Swap(arr, mid, left)
if arr[right] < arr[mid]:
Swap(arr, right, mid)
return mid
# Generic Swap for manipulating list data.
def Swap(arr, left, right):
temp = arr[left]
arr[left] = arr[right]
arr[right] = temp