algorithm - codigo - Quicksort vs heapsort
heapsort python codigo (11)
Bueno, si vas al nivel de la arquitectura ... usamos la estructura de datos de la cola en la memoria caché. Así, lo que está disponible en la cola será ordenado. Como en el ordenamiento rápido no tenemos problemas para dividir la matriz en cualquier longitud ... pero en montón sort (mediante el uso de una matriz) puede ocurrir que el elemento primario no esté presente en la matriz secundaria disponible en la memoria caché y luego tenga que ponerlo en la memoria caché ... lo que consume mucho tiempo. Eso es quicksort es lo mejor !! 😀
Tanto el quicksort como el heapsort realizan la clasificación in situ. ¿Cual es mejor? ¿Cuáles son las aplicaciones y los casos en que se prefiere?
Comp. entre quick sort y merge sort ya que ambas son tipo de ordenamiento in situ, existe una diferencia entre el tiempo de ejecución de caso de wrost del tiempo de ejecución de caso de wrost para ordenación rápida es O(n^2) y para el ordenamiento de montón todavía es O(n*log(n)) y para una cantidad promedio de datos de clasificación rápida será más útil. Dado que se trata de un algoritmo aleatorizado, la probabilidad de obtener ans correctas es mayor. en menos tiempo dependerá de la posición del elemento de pivote que elija.
Entonces una
Buena llamada: los tamaños de L y G son cada uno menos de 3s / 4
Mala llamada: una de L y G tiene un tamaño mayor que 3s / 4
para una pequeña cantidad podemos ir para la ordenación de inserción y para una gran cantidad de datos ir para la ordenación de montón.
Heap Sort es una apuesta segura cuando se trata de entradas muy grandes. El análisis asintótico revela el orden de crecimiento de Heapsort en el peor de los casos es Big-O(n logn) , que es mejor que Big-O(n^2) de Quicksort Big-O(n^2) como el peor de los casos. Sin embargo, Heapsort es algo más lento en la práctica en la mayoría de las máquinas que una ordenación rápida bien implementada. Heapsort tampoco es un algoritmo de clasificación estable.
El motivo heapsort es más lento en la práctica que el quicksort debido a la mejor localidad de referencia (" https://en.wikipedia.org/wiki/Locality_of_reference ") en quicksort, donde los elementos de datos se encuentran dentro de ubicaciones de almacenamiento relativamente cercanas. Los sistemas que muestran una fuerte localidad de referencia son excelentes candidatos para la optimización del rendimiento. El tipo de montón, sin embargo, se ocupa de saltos más grandes. Esto hace que quicksort sea más favorable para entradas más pequeñas.
Heapsort es O (N log N) garantizado, lo que es mucho mejor que el peor caso en Quicksort. Heapsort no necesita más memoria para otra matriz para poner datos ordenados como lo necesita Mergesort. Entonces, ¿por qué las aplicaciones comerciales se quedan con Quicksort? ¿Qué Quicksort tiene que es tan especial sobre otras implementaciones?
He probado los algoritmos yo mismo y he visto que Quicksort tiene algo especial. Funciona rápido, mucho más rápido que los algoritmos Heap and Merge.
El secreto de Quicksort es: casi no hace intercambios innecesarios de elementos. El intercambio lleva mucho tiempo.
Con Heapsort, incluso si todos sus datos ya están ordenados, va a cambiar el 100% de los elementos para ordenar la matriz.
Con Mergesort, es incluso peor. Va a escribir el 100% de los elementos en otra matriz y volver a escribirla en la original, incluso si los datos ya están ordenados.
Con Quicksort no intercambias lo que ya está ordenado. Si sus datos están completamente ordenados, ¡no intercambia casi nada! Aunque hay mucho alboroto sobre el peor de los casos, una pequeña mejora en la elección del pivote, cualquiera que no sea obtener el primer elemento o el último elemento del conjunto, puede evitarlo. Si obtienes un pivote del elemento intermedio entre el primer elemento, el último y el medio, es suficiente para evitar el peor de los casos.
Lo que es superior en Quicksort no es el peor de los casos, ¡sino el mejor! En el mejor de los casos, haga el mismo número de comparaciones, vale, pero no intercambia casi nada. En el caso promedio, intercambiamos parte de los elementos, pero no todos, como en Heapsort y Mergesort. Eso es lo que le da a Quicksort el mejor momento. Menos intercambio, más velocidad.
La implementación a continuación en C # en mi computadora, ejecutándose en modo de lanzamiento, supera a Array.Sort por 3 segundos con pivote medio y por 2 segundos con pivote mejorado (sí, hay una sobrecarga para obtener un buen pivote).
static void Main(string[] args)
{
int[] arrToSort = new int[100000000];
var r = new Random();
for (int i = 0; i < arrToSort.Length; i++) arrToSort[i] = r.Next(1, arrToSort.Length);
Console.WriteLine("Press q to quick sort, s to Array.Sort");
while (true)
{
var k = Console.ReadKey(true);
if (k.KeyChar == ''q'')
{
// quick sort
Console.WriteLine("Beg quick sort at " + DateTime.Now.ToString("HH:mm:ss.ffffff"));
QuickSort(arrToSort, 0, arrToSort.Length - 1);
Console.WriteLine("End quick sort at " + DateTime.Now.ToString("HH:mm:ss.ffffff"));
for (int i = 0; i < arrToSort.Length; i++) arrToSort[i] = r.Next(1, arrToSort.Length);
}
else if (k.KeyChar == ''s'')
{
Console.WriteLine("Beg Array.Sort at " + DateTime.Now.ToString("HH:mm:ss.ffffff"));
Array.Sort(arrToSort);
Console.WriteLine("End Array.Sort at " + DateTime.Now.ToString("HH:mm:ss.ffffff"));
for (int i = 0; i < arrToSort.Length; i++) arrToSort[i] = r.Next(1, arrToSort.Length);
}
}
}
static public void QuickSort(int[] arr, int left, int right)
{
int begin = left
, end = right
, pivot
// get middle element pivot
//= arr[(left + right) / 2]
;
//improved pivot
int middle = (left + right) / 2;
int
LM = arr[left].CompareTo(arr[middle])
, MR = arr[middle].CompareTo(arr[right])
, LR = arr[left].CompareTo(arr[right])
;
if (-1 * LM == LR)
pivot = arr[left];
else
if (MR == -1 * LR)
pivot = arr[right];
else
pivot = arr[middle];
do
{
while (arr[left] < pivot) left++;
while (arr[right] > pivot) right--;
if(left <= right)
{
int temp = arr[right];
arr[right] = arr[left];
arr[left] = temp;
left++;
right--;
}
} while (left <= right);
if (left < end) QuickSort(arr, left, end);
if (begin < right) QuickSort(arr, begin, right);
}
Heapsort tiene la ventaja de tener el peor caso de O (n * log (n)), por lo que, en los casos en que es probable que el quicksort tenga un rendimiento deficiente (en general, los conjuntos de datos ordenados), el heapsort es muy preferido.
Los híbridos Quicksort-Heapsort in-place también son muy interesantes, ya que la mayoría de ellos solo necesitan comparaciones n * log n en el peor de los casos (son óptimos con respecto al primer término de los asintóticos, por lo que evitan los peores escenarios de Quicksort), O (log n) espacio extra y conservan al menos "una mitad" del buen comportamiento de Quicksort con respecto al conjunto de datos ya ordenado. Dikert y Weiss presentan un algoritmo extremadamente interesante en http://arxiv.org/pdf/1209.4214v1.pdf :
- Seleccione un pivote p como la mediana de una muestra aleatoria de elementos sqrt (n) (esto se puede hacer en la mayoría de las 24 cuadrículas (n) comparaciones a través del algoritmo de Tarjan & co, o 5 sqrt (n) comparaciones a través de la araña mucho más intrincada -factory algoritmo de Schonhage);
- Particiona tu matriz en dos partes como en el primer paso de Quicksort;
- Heapify la parte más pequeña y utiliza O (log n) bits adicionales para codificar un montón en el que cada niño izquierdo tiene un valor mayor que su hermano;
- Extraiga recursivamente la raíz del montón, deslice hacia abajo la laúd que deja la raíz hasta que llegue a una hoja del montón, luego llene la laguna con un elemento apropiado tomado de la otra parte de la matriz;
- Vuelve sobre la parte no ordenada restante de la matriz (si p se elige como la mediana exacta, no hay recursividad en absoluto).
Para la mayoría de las situaciones, tener rápido versus un poco más rápido es irrelevante ... simplemente nunca querrás que se vuelva lento de vez en cuando. Aunque puede ajustar QuickSort para evitar situaciones lentas, pierde la elegancia del QuickSort básico. Entonces, para la mayoría de las cosas, realmente prefiero HeapSort ... puedes implementarlo en su elegancia completamente simple, y nunca obtener una clasificación lenta.
En situaciones en las que QUIERE la velocidad máxima en la mayoría de los casos, es posible que se prefiera QuickSort a HeapSort, pero ninguna de las dos es la respuesta correcta. Para situaciones de velocidad crítica, vale la pena examinar de cerca los detalles de la situación. Por ejemplo, en algunos de mis códigos de velocidad crítica, es muy común que los datos ya estén clasificados o casi ordenados (está indexando múltiples campos relacionados que a menudo se mueven hacia arriba y hacia abajo juntos O se mueven hacia arriba y hacia abajo opuestos, así que una vez que clasifique por uno, los otros estarán ordenados o ordenados de forma inversa o cerrados ... cualquiera de los cuales puede matar a QuickSort). Para ese caso, no implementé ... en su lugar, implementé SmoothSort de Dijkstra ... una variante de HeapSort que es O (N) cuando ya está ordenada o casi clasificada ... no es tan elegante, no es muy fácil de entender, pero rápido ... lee http://www.cs.utexas.edu/users/EWD/ewd07xx/EWD796a.PDF si quieres algo un poco más difícil de codificar.
Para mí hay una diferencia fundamental entre heapsort y quicksort: este último usa una recursión. En algoritmos recursivos, el montón crece con el número de recurrencias. Esto no importa si n es pequeño, pero ahora estoy ordenando dos matrices con n = 10 ^ 9. El programa requiere casi 10 GB de RAM y cualquier memoria extra hará que mi computadora comience a intercambiar a la memoria del disco virtual. Mi disco es un disco RAM, pero seguir intercambiándolo hace una gran diferencia en la velocidad . Así que en un paquete de estadísticas codificado en C ++ que incluye matrices de dimensiones ajustables, con un tamaño desconocido por adelantado para el programador, y un tipo estadístico no paramétrico de ordenamiento, prefiero el heapsort para evitar retrasos en el uso con matrices de datos muy grandes.
Para responder la pregunta original y abordar algunos de los otros comentarios aquí:
Acabo de comparar las implementaciones de selección, rápida, fusión y clasificación de montón para ver cómo se comparan entre sí. La respuesta es que todos tienen sus desventajas.
TL; DR: Quick es el mejor tipo de propósito general (razonablemente rápido, estable y sobre todo en el lugar) Personalmente, prefiero el tipo de ordenamiento, a menos que necesite un tipo estable.
Selección - N ^ 2 - En realidad solo es bueno para menos de 20 elementos, y luego se supera. A menos que sus datos ya estén clasificados, o muy, muy cerca. N ^ 2 se pone realmente lento muy rápido.
Rápido, en mi experiencia, en realidad no es tan rápido todo el tiempo. Sin embargo, las bonificaciones por usar el método de clasificación rápida son relativamente rápidas y estables. También es un algoritmo en el lugar, pero como generalmente se implementa recursivamente, ocupará espacio de pila adicional. También se encuentra entre O (n log n) y O (n ^ 2). El tiempo en algunos géneros parece confirmar esto, especialmente cuando los valores caen dentro de un rango estrecho. Es mucho más rápido que la selección, ordena en 10,000,000 de artículos, pero más lento que fusionar o acumular.
La clasificación de fusión está garantizada O (n log n) ya que su clasificación no depende de los datos. Simplemente hace lo que hace, independientemente de los valores que le hayas otorgado. También es estable, pero los géneros muy grandes pueden explotar tu pila si no tienes cuidado con la implementación. Existen algunas implementaciones complejas de ordenamiento por fusión in situ, pero en general necesita otra matriz en cada nivel para fusionar sus valores. Si esas matrices viven en la pila, puede tener problemas.
La ordenación en montón es max O (n log n), pero en muchos casos es más rápida, dependiendo de qué tan lejos tenga que mover sus valores hasta el log n deep heap. El montón se puede implementar fácilmente en el lugar en la matriz original, por lo que no necesita memoria adicional, y es iterativo, por lo que no se preocupe por el desbordamiento de la pila mientras se repiten. La gran desventaja de la clasificación de montón es que no es un tipo estable, lo que significa que es correcto si lo necesita.
Heapsort construye un montón y luego extrae repetidamente el elemento máximo. Su peor caso es O (n log n).
Pero si vieras el peor caso de ordenación rápida , que es O (n2), te darías cuenta de que la clasificación rápida sería una opción no tan buena para datos grandes.
Así que esto hace que la clasificación sea algo interesante; Creo que la razón por la que tantos algoritmos de clasificación viven en la actualidad es porque todos son "mejores" en sus mejores lugares. Por ejemplo, sort de burbuja puede realizar una clasificación rápida si los datos están ordenados. O si sabemos algo sobre los artículos que se ordenarán, probablemente podamos hacerlo mejor.
Puede que esto no responda tu pregunta directamente, pensé que agregaría mis dos centavos.
http://www.cs.auckland.ac.nz/~jmor159/PLDS210/qsort3.html tiene algunos análisis.
Además, de Wikipedia:
El competidor más directo de quicksort es heapsort. Heapsort es típicamente algo más lento que el quicksort, pero el peor tiempo de ejecución es siempre Θ (nlogn). El Quicksort suele ser más rápido, aunque existe la posibilidad de que se produzca el peor de los casos, excepto en la variante introsort, que cambia a heapsort cuando se detecta un caso grave. Si se sabe de antemano que heapsort va a ser necesario, usarlo directamente será más rápido que esperar a que introsort cambie a él.