#include <stdio.h>
#include <stdlib.h>
#include <math.h>

/* ============================================================
   RETURNS THE MAX ELEMENT FROM A VECTOR
   ============================================================ */
int getMax(int size, int elements[]){

	int i;
	int max = elements[0];

	for(i=1; i<size; i++){
		if(elements[i] > max)
			max = elements[i];
	}

	return(max);
}


/* ============================================================
   RETURNS THE MIN ELEMENT FROM A VECTOR
   ============================================================ */
int getMin(int size, int elements[]){

	int i;
	int min = elements[0];

	for(i=1; i<size; i++){
		if(elements[i] < min)
			min = elements[i];
	}

	return(min);
}


/* ============================================================
   RETURNS THE NUMBER OF DIGITS FROM AN INTEGER
   ============================================================ */
int getNumberDigits(int num){

	int numDigits, intPart;
	float divNum, frac;
	numDigits = 0;
	intPart = num;

	if(num <= 0){
		numDigits = 1;
	}
	else{
		while(intPart > 0){
			divNum = intPart / 10;
			intPart = (int)divNum;
			frac = divNum - intPart;
			numDigits++;
		}
	}

	return(numDigits);
}


/* ============================================================
   RETURNS THE ITH DIGIT OF A NUMBER
   ============================================================ */
int returnDigit(int num, int posDigit){

	int i, intPart, digit;
    float divNum, frac, result;
	intPart = num;

	for(i=0;i<=posDigit;i++){
		divNum = (float)intPart / 10;
		intPart = (int)divNum;
		frac = divNum - intPart;
		result = round(frac * 10);
	}

	digit = (int)result;

	return(digit);
}


/* ============================================================
   SELECT SORT
   ============================================================ */
void selectSort(int v[], int size){
    int i, j, min, x;
    for(i=0;i<size;i++){
        min = i;
        for(j=i+1;j<size;j++){
            if(v[j] < v[min])
                min = j;
        }
        x = v[min];
        v[min] = v[i];
        v[i] = x;
    }
}

/* ============================================================
   BUCKET SORT
   ============================================================ */
void bucketSort(int v[], int size){

	printf("\n========== BUCKET SORT ==============");

	int i, j, k, l, **buckets, numElements, *sortedBucked;
	int numBuckets = 22;
	int intervals[numBuckets-1];
	int sizeBuckets = 100;

	//Mim and max elements to get the intervals of the buckets
	int max = getMax(size,v);
	int min = getMax(size,v);
	numElements = (max-min)+1;

	//Vector of intervals. There will be 10 bucktes for negative
	//numbers and 10 buckets for positive numbers
	j=0;
	for(i=-10;i<=10;i++){
		intervals[j] = i*10;
		j++;
	}

	//Create the buckets
	buckets = (int **)malloc(numBuckets * sizeof(int *));
	for(i=0;i<numBuckets;i++){
		buckets[i] = (int *)malloc(sizeBuckets * sizeof(int));
	}
	for(i=0;i<numBuckets;i++){
		for(j=0;j<sizeBuckets;j++){
			buckets[i][j] = 0;
		}
	}

	//Put the elements in the buckets
	for(i=0;i<size;i++){
		k=0;
		for(j=-10;j<=10;j++){
			if(v[i] >= j*10){
				k++;
			}
			else{
				break;
			}
		}
		//Put elements in the bucket
		for(l=1;l<=buckets[k][0];l++){
		}
		buckets[k][l] = v[i];
		buckets[k][0]++;
	}

	//Sort the buckets with a sorting algorithm
	for(i=0;i<numBuckets;i++){
		if(buckets[i][0] > 0){

			//Put the elements in a vector to be sorted
			sortedBucked = (int *)malloc(buckets[i][0] * sizeof(int));
			for(j=1;j<=buckets[i][0];j++){
				sortedBucked[j-1] = buckets[i][j];
			}

			//Sort the elements of the bucket
			selectSort(sortedBucked,buckets[i][0]);

			//Put the elements back to the bucket
			for(j=1;j<=buckets[i][0];j++){
                buckets[i][j] = sortedBucked[j-1];
            }
			free(sortedBucked);
		}
	}

	//Iterate over the buckets to put elements back to the original list
	k = 0;
	for(i=0;i<numBuckets;i++){
		if(buckets[i][0] > 0){
			for(j=1;j<=buckets[i][0];j++){
				v[k] = buckets[i][j];
				k++;
			}
		}
	}

	free(buckets);
}

/* ============================================================
   PIGEONHOLE SORT
   ============================================================ */
void pigeonholeSort(int v[], int size){

	printf("\n========== PIGEONHOLE SORT ==============");

	int i, j, k, sizePG, **pigeonhole;

	//Min and max elements
	int max = getMax(size,v);
	int min = getMin(size,v);

	//Create the pigeonhole
	sizePG = (max-min)+2;
	pigeonhole = (int **)malloc((sizePG-1) * sizeof(int *));
	for(i=0;i<(sizePG-1);i++){
		pigeonhole[i] = (int *)malloc(sizePG * sizeof(int));
	}
	for(i=0;i<(sizePG-1);i++){
		for(j=0;j<sizePG;j++){
			pigeonhole[i][j] = 0;
		}
	}

	//Put the elements in the pigeonholes
	for(i=0;i<size;i++){
		//Put elements in the pigeonhole
		for(j=1;j<=pigeonhole[v[i]-min][0];j++){
		}
		pigeonhole[v[i]-min][j] = v[i];
		pigeonhole[v[i]-min][0]++;
	}

	//Iterate over the pigeonhole to put elements back to the original list
	k = 0;
	for(i=0;i<(sizePG-1);i++){
		if(pigeonhole[i][0] > 0){
			for(j=1;j<=pigeonhole[i][0];j++){
				v[k] = pigeonhole[i][j];
				k++;
			}
		}
	}

	free(pigeonhole);
}


/* ============================================================
   RADIX SORT
   ============================================================ */
void radixSort(int v[], int size){

	printf("\n========== RADIX SORT ==============");

	int i, j, k, l, **buckets, digit;


	//Add the positive min elements to all numbers
	//This is done to handle negative values
	int min = getMin(size,v);
	if(min < 0){
		min = min*-1;
	}
	for(i=0;i<size;i++){
		v[i] += min;
	}

	//Get the max element to
	//Necessary to count the number of digits
	int max = getMax(size,v);

	//Get the number of digits
	int numDigits = getNumberDigits(max);

	//Create 10 buckets, one for each possible digit of a number
	buckets = (int **)malloc(10 * sizeof(int *));
    for(i=0;i<10;i++){
        buckets[i] = (int *)malloc(size * sizeof(int));
    }
    for(i=0;i<10;i++){
        for(j=0;j<size;j++){
            buckets[i][j] = 0;
        }
    }

	//Put elements in the buckets according to its digits
	//from the LSD to the MSD
	for(i=0;i<numDigits;i++){
		for(j=0;j<size;j++){

			//Returns the ith digit of the number
			digit = returnDigit(v[j],i);

			//Put elements in the bucket
			for(k=1;k<=buckets[digit][0];k++){
			}
			buckets[digit][k] = v[j];
			buckets[digit][0]++;

		}

		//Put the elements back into the original array
		k = 0;
		for(l=0;l<10;l++){
			if(buckets[l][0] > 0){
				for(j=1;j<=buckets[l][0];j++){
					v[k] = buckets[l][j];
					k++;
				}
			}
		}

		//Set the buckets empty
		for(k=0;k<10;k++){
        	for(l=0;l<size;l++){
            	buckets[k][l] = 0;
	        }
    	}
	}

	//Decrement min from all values to recover original values
	for(i=0;i<size;i++){
		v[i] -= min;
	}

	free(buckets);

}

/* ============================================================
   COUNTING SORT
   ============================================================ */
void countingSort(int v[], int size){

	printf("\n========== COUNTING SORT ==============");

	int i, j, k, sizeCount, *counting;

	//Min and max elements
	int max = getMax(size,v);
	int min = getMin(size,v);

	//Create a vector to store counts
	sizeCount = (max-min)+1;
	counting = (int *)malloc(sizeCount * sizeof(int));
	for(i=0;i<sizeCount;i++){
		counting[i] = 0;
	}

	//Here we count the elements
	for(i=0;i<size;i++){
		counting[v[i]-min]++;
	}

	//Iterate over the vector to put elements of the original list in order
	j = 0;
	for(i=0;i<sizeCount;i++){
		if(counting[i] > 0){
			for(k=0; k<counting[i]; k++){
				v[j] = min+i;
				j++;
			}
		}
	}

	free(counting);
}


/* ============================================================
   GET THE NUMBERS FROM THE USER AND CALL SORTING ALGORITHM
   ============================================================ */
void createVector(int op){

	int i, num, tam, *vector, a;

	printf("How many elements: ");
	scanf("%d",&tam);

	vector = (int *)malloc(tam * sizeof(int));

	for(i=0;i<tam;i++){
		printf("Enter an integer number: ");
		scanf("%d",&num);
		vector[i] = num;
	}

	switch(op){
		case 1: countingSort(vector,tam);
			break;
		case 2: pigeonholeSort(vector,tam);
			break;
		case 3: bucketSort(vector,tam);
			break;
		case 4: radixSort(vector,tam);
			break;
	}

	printf("\n=================================\n");
	printf("Sorted vector: ");

	for(a=0;a<tam;a++){
		printf("%d ",vector[a]);
	}
	printf("\n=================================\n");
	printf("\n\n\n");

	free(vector);
	vector = NULL;
}

/* ============================================================
   PRINTS THE MENU FOR CHOOSING THE SORTING ALGORITHMS
   ============================================================ */
void menu(){

	printf("\nChoose method!\n");
	printf("1 -> Counting Sort\n");
	printf("2 -> Pigeonhole Sort\n");
	printf("3 -> Bucket Sort\n");
	printf("4 -> Radix Sort\n");
	printf("5 -> Sair\n");

}


/* ============================================================
   MAIN FUNCTION
   ============================================================ */
int main(){

	int option;

	while(option != 5){

		menu();

		scanf("%d",&option);

		switch(option){

			case 1: createVector(1);
				break;
			case 2: createVector(2);
				break;
			case 3: createVector(3);
				break;
			case 4: createVector(4);
				break;
			default: option = 5;
				break;
		}
	}

	return EXIT_SUCCESS;
}