bucketsort.cpp

Bài toán

Sắp xếp một dãy số nguyên với các phần tử nằm trong khoảng 1..1000000 bằng bucket sort và counting sort.

Độ phức tạp

O(n+B*B) trong đó B là số bucket

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 N 1000006

#define B 1024

void count_sort(int a[], int n) {

    static int a1[N], First[B], Last[B], Count[B];

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

        First[i] = Last[i] = Count[i] = 0;

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

        Count[a[i] % B]++;

    for (int i = 1; i <= B - 1; ++i)

        Last[i] = First[i] = First[i - 1] + Count[i - 1];

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

        a1[++Last[a[i] % B]] = a[i];

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

        a[i] = a1[i];

}

void bucket_sort(int a[], int n) {  // 1-based

    static int a1[N], First[B], Last[B], Count[B];

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

        First[i] = Last[i] = Count[i] = 0;

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

        Count[a[i] >> 10]++;

    for (int i = 1; i <= B - 1; ++i)

        Last[i] = First[i] = First[i - 1] + Count[i - 1];

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

        a1[++Last[a[i] >> 10]] = a[i];

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

        count_sort(a1 + First[i], Count[i]);

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

        a[i] = a1[i];

}

int n, a[N];

int main() {

    scanf("%d", &n);

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

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

    bucket_sort(a, n);

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

        printf("%d\n", a[i]);

}

Nhận xét