balls_and_bins.c

// Zachary Thompson
// Idea from "The Algorithm Design Manual" by Skiena page 179
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

#define N 100000000

int main() {
	int *arr = malloc(sizeof(int) * N);
	memset(arr, 0, sizeof(int) * N);

	srand(time(NULL));
	for (int i = 0; i < N; i++) {
		int index = rand() % N;
		arr[index]++;
	}
	int count = 0;
	printf("n=%d\n", N);
	printf("\e[4mk\tBuckets w/ k Items\e[24m\n");
	for (int k = 0; k < 15; k++) {
		for (int i = 0; i < N; i++) {
			if (arr[i] == k) {
				count++;
			}
		}
		printf("%d\t%d\n", k, count);
		count = 0;
	}
	free(arr);
}