Сортировка по основанию медленнее, чем Быстрая сортировка?

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.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).Для n = 52428800, log(n) = 17.Затем я ожидаю, что сортировка по основанию будет в 3 раза быстрее, чем Быстрая сортировка...

Это не то, что я наблюдаю.

Что я упускаю из виду?

Answer 1

1. qsort - это не Быстрая сортировка.qsort - это то, что решил разработчик стандартной библиотеки.

2. Сортировка 50 миллионов идентичных значений крайне нерепрезентативна.Существуют реализации qsort, которые будут сортировать 50 миллионов идентичных или 50 миллионов отсортированных или наоборот отсортированных элементов за линейное время.

3. Набор из 50 миллионов чисел с шестью цифрами - это очевидная бессмыслица.Шесть цифр означают, что вы ожидаете только 64 различных значения и, следовательно, будете использовать сортировку по счету.С менее чем 26 цифрами это не имеет смысла.

4. Ваша базовая сортировка выполняет ужасно много копирования и, что еще хуже, некэшированное копирование.

5. Ваша сортировка по основанию не дает правильно отсортированного результата, если digits - нечетное число.

6. Ваш вызов qsort не выдает правильно отсортированного результата, если массив содержит очень большие и очень маленькие числа.