Radix Sort (số thực)

Bài toán

Sắp xếp một dãy số thực bằng radix sort.

Độ phức tạp

O(k.(n+B)) với k là số pha radix sort, B là hệ cơ số

(Code dưới đây dùng k=4 và B=65536)

Code này của Nguyễn Tiến Trung Kiên

#include <assert.h>

#include <stdio.h>

#include <algorithm>

#include <iostream>

#include <vector>

using namespace std;

#define long long long

const int B = 65536;

inline long represent(double x) {

    long y = *((long *)&x);

    return y < 0 ? ~y : y | (1LL << 63);

}

inline int h(double x, int k) {

    long p = represent(x);

    return (p >> k) & (B - 1);

}

void radix_sort(vector<double> &a, vector<double> &b, int n, int k) {

    vector<int> Count(B), Start(B);

    for (int i = 0; i < n; i++) Count[h(a[i], k)]++;

    for (int i = 1; i < B; i++) Start[i] = Start[i - 1] + Count[i - 1];

    for (int i = 0; i < n; i++) b[Start[h(a[i], k)]++] = a[i];

}

void radix_sort(vector<double> &a) {

    int n = a.size();

    vector<double> b(n);

    radix_sort(a, b, n, 0);

    radix_sort(b, a, n, 16);

    radix_sort(a, b, n, 32);

    radix_sort(b, a, n, 48);

}

int main() {

    int n;

    scanf("%d", &n);

    vector<double> a(n);

    for (int i = 0; i < n; i++)

        a[i] = 100.0 * rand() / RAND_MAX - 100.0 * rand() / RAND_MAX;

    radix_sort(a);

    //sort(a.begin(), a.end());

    for (int i = 1; i < n; i++)

        assert(a[i] >= a[i - 1]);

    cout << "Done" << endl;

}

Nhận xét

Code này chưa được dùng để nộp cho bất kì bài nào.

Độ nhanh chậm của thuật toán này phụ thuộc nhiều vào kiểu dữ liệu là double hay float.

- Khi kiểu dữ liệu là double, B=65536, thuật toán chạy chậm hơn std::sort.

- Khi kiểu dữ liệu là double, B=256, thuật toán chạy chậm hơn std::sort.

- Khi kiểu dữ liệu là float, B=65536, thuật toán chạy nhanh hơn std::sort.

- Khi kiểu dữ liệu là float, B=256, thuật toán chạy nhanh hơn std::sort.

Đánh giá

Các bạn có thể đánh giá bài viết, yêu cầu giải thích hoặc gửi nhận xét tại đây.

http://goo.gl/forms/k7DsrEZbdd