¿Hay una buena biblioteca para la clasificación de un gran conjunto de números en C?

Question

Si tengo una gran variedad de números enteros o flotadores, lo que es un buen algoritmo / aplicación para la clasificación (en C)?

Es un poco tarde en el juego para una edición ... pero estoy en busca de corrección y velocidad .

Answer 1

Para ordenar matrices de números, considere un algoritmo radix tipo. Cuando diseñados adecuadamente, este tipo deben proporcionar mejor rendimiento que GLIBC qsort ().

La biblioteca usort contiene implementaciones específicas del tipo para todos los principales tipos numéricos C.

http://bitbucket.org/ais/usort/wiki/Home

La ventaja de la velocidad de Radix sort sobre GLIBC qsort es alrededor de 2,5 veces de doble precisión números de punto flotante en N = 1.000.000 en mi portátil Intel de 64 bits. Sin embargo, como N crece la ventaja debe ser aún mayor, ya que radix tipo es un algoritmo de tiempo lineal requiere número constante de pasos por los datos.

Para muy pequeña N, el mismo código despacha a un introsort o inserción tipo.

Answer 2

qsort () de la biblioteca estándar es un good'un.

Las funciones de comparación sería trivial para estos casos:

int cmp_int(const void *a, const void *b)
{
    const int *ia = a;
    const int *ib = b;

    if (*ia < *ib)
        return -1;

    if (*ia > *ib)
        return 1;

    return 0;
}

int cmp_float(const void *a, const void *b)
{
    const float *fa = a;
    const float *fb = b;

    if (*fa < *fb)
        return -1;

    if (*fa > *fb)
        return 1;

    return 0;
}

(EDIT:. La versión de éstos sobre la base de restar b de una se basa en el comportamiento de desbordamiento firmado, así que no es una buena idea)

Answer 3

Nunca es una mala idea usar qsort ... a menos que sepa algo acerca de los números.

Se ha etiquetado con Radix sort. La cantidad de memoria que está dispuesto a invertir? Son los números dentro de un rango específico? ¿Tienen propiedades que hacen que la clasificación radix factible?

A menos que usted desea utilizar una gran cantidad de memoria, qsort es una gran opción.

Answer 4

Teniendo en cuenta una gran cantidad de memoria RAM que estamos recibiendo en la actualidad, el siguiente tipo conjunto es posible: marcar el bit en una enorme matriz de bits de RAM para cada número que tiene, a continuación, leerlos de la espalda mediante el escaneo de la memoria RAM. Un montón de optimizaciones específicas de hardware se pueden aplicar para las fases de exploración y de marca.