基拉兹排序比快速排序慢？

Question

我想证明有时的基数比快速排序更好。在此示例中，我正在使用以下程序：

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

.

它执行如下：

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

.

我知道快速排序将在 o（n log n）中执行，而基数排序将在 o（d（n + r））中〜= <强> O（6 * n）。for n = 52428800，log(n) = 17。然后，我期待基数排序比快速排序快3倍...

这不是我观察到的。

我缺少什么？

Answer 1

1. qsort不是QuickSort。QSORT是标准图书馆的实现者决定的。

2. 排序5000万个相同的值非常不足。有QSORT实现，将在线性时间对5000万相同或5000万排序或反向排序元素进行排序。

3. 六位数的5000万号码显然是胡说八道。六位数意味着您期望只有64个不同的值，因此将使用计数排序。少于26位，它没有意义。

4. 你的基数排序是一个可怕的很多复制，更糟糕的是未加工的复制。

5. 如果数字是奇数，则无线排序不会产生正确排序的结果。

6. 如果阵列包含非常大而非常小的数字，则QSORT呼叫不会产生正确排序的结果。