iframe-proxy | Sunbelt Computer Software

69 lines (61 loc) · 1.01 KB

#include <cstdio>
#include <climits>
#define INF INT_MAX
#define ELEMENT_COUNT 100000
#define ELEMENT_RANGE (1 << 17)
#define GROUP_RANGE (1 << 2)
using namespace std;
int n, d[ELEMENT_COUNT];
struct node
	int v, next;
}A[ELEMENT_COUNT + 1];
int head[ELEMENT_RANGE / GROUP_RANGE], cnt[ELEMENT_RANGE / GROUP_RANGE], vc = 1;
void insert(int v)
	int group = v / GROUP_RANGE;
	A[vc].next = head[group];
	head[group] = vc;
	A[vc].v = v;
	cnt[group]++;
void bucket_sort()
	for (int i = 0; i < n; i++)
		insert(d[i]);
	int ptr = 0;
	for (int i = 0; i < ELEMENT_RANGE / GROUP_RANGE; i++)
		for (int j = 0; j < cnt[i]; j++)
			int minv = INF, ord;
			for (int cur = head[i]; cur != 0; cur = A[cur].next)
				if (A[cur].v < minv)
					minv = A[cur].v;
					ord = cur;
			d[ptr++] = minv;
			A[ord].v = INF;
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
		scanf("%d", &d[i]);
	bucket_sort();
	for (int i = 0; i < n; i++)
		printf("%d ", d[i]);

Sunbelt Computer Software

PL/B Language Development and Support

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

Sunbelt Computer Software

PL/B Language Development and Support

Uh oh!

FilesExpand file tree

Bucket-Sort.cpp

Latest commit

History

Bucket-Sort.cpp

File metadata and controls