radixsort.cpp

Bài toán

Sắp xếp không giảm một dãy số nguyên duơng.

Độ phức tạp

O(k(n+m)) với m là độ lớn buffer (bộ nhớ ngoài), k là số lượt radix sort (bằng giá trị phần tử lớn nhất chia cho m, cụ thể hơn với dãy số nguyên thì ta chỉ cần k nhỏ chỉ bằng 2,3,4).

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

#include <stdio.h>

#include <algorithm>

#include <iostream>

using namespace std;

#define long long long

#define f1(i, n) for (int i = 1; i <= n; i++)

#define f0(i, n) for (int i = 0; i < n; i++)

#define N 1000006

int n, a[N], b[N];

void radix_sort(int a[], int b[], int n, int pos) {

    int Count[256] = {}, Start[256] = {};

    f1(i, n) Count[char(a[i] >> pos) & 255]++;

    f1(i, 255) Start[i] = Start[i - 1] + Count[i - 1];

    f1(i, n) b[++Start[(a[i] >> pos) & 255]] = a[i];

}

int main() {

    int t = 0;

    scanf("%d", &t);

    while (t--) {

        scanf("%d", &n);

        f1(i, n) {

            scanf("%d", &a[i]);

            if (a[i] == 1) a[i] = 0x3c3c3c3c;

        }

        radix_sort(a, b, n, 0);

        radix_sort(b, a, n, 8);

        radix_sort(a, b, n, 16);

        radix_sort(b, a, n, 24);

        //  sort(a+1, a+n+1);

        reverse(a + 1, a + n + 1);

        f1(i, n) {

            if (a[i] == 0x3c3c3c3c)

                a[i] = 1;

            else {

                if (a[i] == 3 && a[i + 1] == 2) swap(a[i], a[i + 1]);

                break;

            }

        }

        f1(i, n) printf(i == n ? "%d\n" : "%d ", a[i]);

    }

}

Mô tả

void radix_sort(int a[], int b[], int n, int pos)

sắp xếp mảng a và trả về kết quả vào mảng b, a là input, b là output, n là số phần tử, pos là số hiệu chữ số đang xét (ở đây ta dùng hệ cơ số 256, pos nằm trong tập {0,8,16,24} tương ứng với chữ số thứ 0,1,2,3).

Nhận xét

Code này đã được dùng để nộp cho một bài tập trên SPOJ.

Kết quả cho thấy 4 câu lệnh gọi radixsort trong main cho kết quả tương đương với việc dùng hàm std::sort.

Tham khảo

http://www.spoj.com/problems/ARRANGE/