radix sort sort solut flower보다 빠른 정렬?

Question

언젠가 radix- 정렬이 빠른 정렬보다 낫다는 것을 보여주고 싶습니다.이 예에서는 아래 프로그램을 사용하고 있습니다 :

#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

.

Radix Sort가 o (d (n + r)) ~= o (6 * n) .n = 52428800, log(n) = 17.그런 다음 Radix 종류가 빠른 정렬보다 3 배 빠르게 예상됩니다 ...

이것은 내가 관찰하는 것이 아닙니다.

누락 된

Answer 1

1. qsort는 QuickSort가 아닙니다.QSORT는 표준 라이브러리의 구현자가 결정된 것입니다.

2. 5000 만 명의 동일한 값을 분류하는 것이 비 표정이 높습니다.선형 시간으로 5,000 만명의 동일하거나 5 천만 정도 정렬 된 요소를 정렬하거나 정렬 된 요소를 정렬하는 QSORT 구현이 있습니다.

3. radix는 6 자리 숫자가 5,000 만 숫자가 분명히 말도 안되는 것입니다.6 자리 숫자는 64 개의 다른 값만 기대하고 계산 정렬을 사용할 것입니다.26 자리 미만이면이 의미가 없습니다.

4. 기기 정렬은 끔찍한 복사, 악화되며 악화 된 복사를 많이합니다.

5. 숫자가 홀수 인 경우 RADIX 정렬이 올바르게 정렬 된 결과를 생성하지 않습니다.

6. 배열에 매우 크고 매우 작은 숫자가 포함되어 있으면 QSORT 호출이 올바르게 정렬 된 결과를 생성하지 않습니다.