quicksort en C ++ es lento

Question

Tengo 9 valores en forma de matriz y necesito calcular la mediana a partir de estos valores como parte de un proceso de simulación.

Uso quicksort en C ++ (es decir, qsort ()), lo que hace que el proceso se ejecute lentamente (ya que este proceso se repite varias veces).

¿Hay un mejor algoritmo de clasificación que podría usar?

Answer 1

La clasificación para obtener una mediana es muy ineficiente. Podrías usar STL nth_element en su lugar:

#include <algorithm>

// Assuming you keep the elements in a vector v of size len

std::nth_element( v.begin(), v.begin()+len/2, v.end() );
median = v[len/2];

 //... or, if the elements are in a simple array v[len], then

std::nth_element( v, v+len/2, v+len );
median = v[len/2];

Nota: el nth_element modificará el vector / array v. Haga una copia primero si necesita conservar el original.

Answer 2

Por favor, por favor, nunca recomiende el tipo de burbuja excepto a los masoquistas!

Para valores pequeños, la clasificación inserción es la mejor, y es buena para otras aplicaciones (datos casi ordenados de cualquier longitud).

Editar: limpie el formato, enfatizando la respuesta sugerida.

Answer 3

¿Sólo 9 valores? Quicksort es una exageración.

Tal vez utilice la ordenación por inserción, la ordenación por burbuja u otros algoritmos de clasificación más simples cuando trabaje con conjuntos de datos más pequeños.

Rendimiento

El orden de burbuja tiene una complejidad en el peor de los casos y en el medio & # 1054; (n & # 178;), donde n es el número de elementos que se ordenan. Existen muchos algoritmos de clasificación con una complejidad sustancialmente mejor en el peor de los casos o en el promedio de O (n log n). Incluso otros algoritmos de clasificación & # 1054; (n & # 178;), como la clasificación por inserción, tienden a tener un mejor rendimiento que la clasificación por burbuja. Por lo tanto, la ordenación por burbuja no es un algoritmo práctico de clasificación cuando n es grande.

Sin embargo, concedido, ni siquiera tuvo que ordenar para obtener la mediana como otros han sugerido.

Answer 4

1. Como mencionó onebyone, no es necesario clasificar por completo para obtener una mediana.

2. STL tiene el algoritmo sort que generalmente puede realizar la comparación en línea. También tiene un algoritmo más inteligente que el garantizado por qsort, con worstcase de O (NlgN).

Answer 5

Usar quicksort para solo 9 valores será bastante ineficiente. Para un tamaño de muestra tan pequeño, es mucho mejor utilizar una clasificación por selección o una clasificación de reemplazo ... hay muy pocos gastos generales en estos métodos de clasificación.

Quicksort y Mergesort realmente brillan una vez que el tamaño de su muestra alcanza un umbral, quizás 50+.

En estas situaciones, escribiría mi propio código en lugar de utilizar una función incorporada.

Answer 6

El algoritmo std :: sort () es casi siempre preferible a qsort (). Normalmente es más fácil de usar y se ejecuta más rápido.

Si desea entrar en detalles, en realidad hay una familia de algoritmos de clasificación. Stroustrup escribe en The C ++ Programming Language que std :: sort no suele ser exactamente lo que se debe usar. En este caso, std :: nth_element () es probablemente lo que quieres.

Answer 7

No tiene suficientes valores para trabajar con Quicksort y debe usar algoritmos menos avanzados (por ejemplo, clasificación de burbuja, clasificación de inserción, ... explicación aquí .

Hay un costo asociado a la configuración de Quicksort y cuando no tienes suficientes valores, es inútil usar esta bestia.

Answer 8

Tipo de inserción ..

En conjuntos de datos pequeños, puede utilizar diferentes algoritmos para obtener un rendimiento óptimo. QuickSort brilla una vez que el conjunto de datos crece.

Hay diferentes enfoques. Puede utilizar las estructuras de datos donde clasifica en la inserción, y hay una vez que ordena el conjunto de datos completo. Solo necesitas encontrar tu algoritmo óptimo.