Radix-Sortierung langsamer als Schnellsortierung?

Question

Ich möchte zeigen, dass Radix-Sort manchmal besser ist als Quick-Sort.In diesem Beispiel verwende ich das folgende Programm:

#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());
}

Es funktioniert wie folgt:

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

Ich weiß, dass Quick Sort funktionieren wird O(n log n) während Radix Sort dabei sein wird O(d (n + r)) ~= O(6 * n).Für n = 52428800, log(n) = 17.Ich erwarte dann, dass Radix Sort dreimal schneller ist als Quick Sort ...

Das ist nicht das, was ich beobachte.

Was vermisse ich?

Answer 1

1. qsort ist kein Quicksort.qsort ist das, was der Implementierer der Standardbibliothek entschieden hat.

2. Das Sortieren von 50 Millionen identischen Werten ist höchst unrepräsentativ.Es gibt qsort-Implementierungen, die 50 Millionen identische oder 50 Millionen sortierte oder umgekehrt sortierte Elemente in linearer Zeit sortieren.

3. Eine Art Radix von 50 Millionen Zahlen mit sechs Ziffern ist offensichtlich Unsinn.Sechs Ziffern bedeuten, dass Sie nur 64 verschiedene Werte erwarten und daher die Zählsortierung verwenden würden.Bei weniger als 26 Ziffern macht es keinen Sinn.

4. Ihre Radix-Sortierung führt eine Menge Kopiervorgänge durch, und schlimmer noch, nicht zwischengespeicherte Kopiervorgänge.

5. Ihre Basissortierung liefert kein korrekt sortiertes Ergebnis, wenn es sich bei den Ziffern um eine ungerade Zahl handelt.

6. Ihr qsort-Aufruf liefert kein korrekt sortiertes Ergebnis, wenn das Array sehr große und sehr kleine Zahlen enthält.