#include <stdio.h>
#include <stdlib.h>
#include <windows.h>
int exch = 0, comp = 0;
#define D 1000
#define RAND(D) rand()%D

void Bucket_Sort(int array[], int n);
int best_array(int a[], int n);
int avg_array(int a[], int n);
int worst_array(int a[], int n);
int printf_array(int a[], int n);

int main() {
	int left = 0;
	printf("Enter n: \n");
	int n, var, k;
	scanf_s("%d", &n);
link:
	printf("Choose the variant:\n1. Best\n2. Avarage\n3. Worst\n");
	scanf_s("%d", &var);
	int *A = new int[n];
	if (var == 1)  // найкращий випадок - масив відсортований;
	{
		best_array(A, n);
		printf_array(A, n);
	}
	else if (var == 2)  // випадковий набір;
	{
		avg_array(A, n);
		printf_array(A, n);
	}
	else if (var == 3)  // найгірший випадок - масив відсортований в зворотньому порядку;
	{
		worst_array(A, n);
		printf_array(A, n);
	}
	else
	{
		printf("Error, try again\n");
		goto link;
	}
	Bucket_Sort(A,n);
	printf_array(A, n);
	printf("\nNumbers of comparisons %d\n", comp);
	printf("Numbers of exchanges %d\n\n", exch);
	system("pause");
}

int best_array(int a[], int n) {
	int i = 0;
	for (int i = 0; i < n; i++) a[i] = i;
	return i;
}

int avg_array(int a[], int n) {
	int i, j, k = 10;
	for (j = 1; j <= k; j++) {
		srand(j);     // srand(13);
		for (i = 0; i < n; i++) a[i] = RAND(D);
	}
	return j;
}

int worst_array(int a[], int n) {
	int i = 0;
	for (int i = 0; i < n; i++) a[i] = n - 1 - i;
	return i;
}

int printf_array(int a[], int n) {
	int i;
	for (i = 0; i < n; i++) printf("%d\t", a[i]);
	printf("\n\n");
	return i;
}

void Bucket_Sort(int array[], int n)
{
	int i, j;
	int* count = new int[n];
	for (i = 0; i < n; i++)
	{
		exch++;
		count[i] = 0;
	}
	for (i = 0; i < n; i++)
	{
		exch++;
		(count[array[i]])++;
	}
	for (i = 0, j = 0; i < n; i++)
	{
		for (; count[i] > 0; (count[i])--)
		{
			exch++;
			array[j++] = i;
		}
	}
}