¿Radix clasifica más lento que el tipo rápido?

Question

Me gustaría demostrar que en algún momento de Radix-Sort es mejor que el tipo rápido.En este ejemplo, estoy usando el programa a continuación:

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h>
#include <time.h>
#include <math.h>

int cmpfunc (const void * a, const void * b) {
   return ( *(int*)a - *(int*)b );
}

void bin_radix_sort(int *a, const long long size, int digits) {
    assert(digits % 2 == 0);

    long long count[2];
    int *b = malloc(size * sizeof(int));
    int exp = 0;

    while(digits--) {
        // Count elements
        count[0] = count[1] = 0;
        for (int i = 0; i < size; i++)
            count[(a[i] >> exp) & 0x01]++;

        // Cumulative sum
        count[1] += count[0];

        // Build output array
        for (int i = size - 1; i >= 0; i--)
            b[--count[(a[i] >> exp) & 0x01]] = a[i];

        exp++;
        int *p = a; a = b; b = p;
    };

    free(b);
}

struct timespec start;

void tic() {
    timespec_get(&start, TIME_UTC);
}

double toc() {
    struct timespec stop;
    timespec_get(&stop, TIME_UTC);
    return stop.tv_sec - start.tv_sec + (
        stop.tv_nsec - start.tv_nsec
    ) * 1e-9;
}

int main(void)
{
    const long long n = 1024 * 1024 * 50;
    printf("Init memory (%lld MB)...\n", n / 1024 / 1024 * sizeof(int));

    int *data = calloc(n, sizeof(int));

    printf("Sorting n = %lld data elements...\n", n);

    long long O;
    tic();
    O = n * log(n);
    qsort(data, n, sizeof(data[0]), cmpfunc);
    printf("%lld %lf s\n", O, toc());

    int d = 6;
    tic();
    O = d * (n + 2);
    bin_radix_sort(data, n, d);
    printf("%lld %lf s\n", O, toc());
}

se realiza de la siguiente manera:

$ gcc bench.c -lm
$ ./a.out 
Init memory (200 MB)...
Sorting n = 52428800 data elements...
931920169 1.858300 s
314572812 1.541998 s

Sé que se realizará un tipo rápido en o (n log n) mientras que Radix Ordenará en O (D (N + R)) ~= O (6 * n) .Para n = 52428800, log(n) = 17.Luego, estoy esperando que Radix sea un tipo 3 veces más rápido que el tipo rápido ...

Esto no es lo que yo observo.

¿Qué estoy perdiendo?

Answer 1

1. qsort no es rápido.QSort es lo que decidió el implementador de la biblioteca estándar.

2. Clasificación de 50 millones de valores idénticos es altamente impresentante.Hay implementaciones QSort que ordenarán 50 millones de elementos idénticos, o 50 millones de elementos ordenados o clasificados inversos en tiempo lineal.

3. Radix de 50 millones de números con seis dígitos es obviamente tonterías.Seis dígitos significa que usted espera solo 64 valores diferentes y, por lo tanto, usaría el recuento.Con menos de 26 dígitos no tiene sentido.

4. TU SORTE DE RADIX Hace una gran cantidad de copia, y peor, copia desconectada.

5. Su clasificación de radix no produce un resultado ordenado correctamente si los dígitos son un número impar.

6. La llamada QSort no produce un resultado ordenado correctamente si la matriz contiene números muy grandes y muy pequeños.