/******************************************
 * Sorting Algorithms in C++
 * (Algo reference: web)
 * 
 * \author Ganesh Viswanathan
 *	   University of Florida, Gainesville
 * \date   Nov 26, 2010
 ******************************************/

#include <iostream>
#include <iomanip> //for using setw() w/ cout
#include <cstdlib> //for using exit() and rand()
#include <ctime> //for seeding the random number generator with srand()
#include <cmath> //for using ceil in radix sort

using namespace std;

int q;
int *tab;

void BubbleSort(int [], const int);
void BubbleSortOptimized(int[], const int); 
void InsertionSort(int [], const int);
void InsertionSorty(int [], const int);
void RadixSort(int [], const int);
void QuickSort(int [], const int);

int compare(int,int);
void swap(int *, int *);
void print(int [], const int);
void random(int);





int compare(int x, int y){
//	cout << "\n x: " << x << ", y: " << y << " => " << (x>y) << endl;
	return ((x>y)?y:0); //false is zero, and true is not-false // returns min
}

void random(int count){
	srand((unsigned) time(0)); //or time(NULL), else pass in a "time_t" object
//	return rand();
//	int lowest=1, range=100;
	for (int i=0; i<count; i++){
//		tab[i]=lowest + int(range*rand()/(RAND_MAX+1));
		tab[i]=(rand()%count)+1;
	}
//	return ((rand() % limit)+1); //If we use rand()%n we generate a number from 0 to n-1
}


void swap(int *x, int *y){// C style
	int temp=*x;
	*x=*y;
	*y=temp;
}

void swapy(int &x, int &y){// C++ style: any type of reference can be used (not just pointers)
//	cout << "\nHELLO FROM C++" << endl;
	int temp=x;
	x=y;
	y=temp;
}

void BubbleSort(int table[], const int size){
	for (int i=0; i<size; i++){
		for (int j=0; j<size-1; j++){
			if ( compare(table[j], table[j+1]) ){
				swap(&table[j], &table[j+1]);
			}
		}
	}
}

void BubbleSortOptimized(int table[], const int size){
	bool swapped=true;
	while(swapped){
		swapped=false;
		for (int i=0; i<size; i++){
			for (int j=0; j<size-1; j++){
	 			if ( compare(table[j], table[j+1]) ){
//					print(table, size);
					swapy(table[j], table[j+1]);
					//swap(&table[j], &table[j+1]); // C Style
					swapped=true;
				}
			}
		}
	}
}

void SelectionSort(int table[], const int size){
	int min=0;// set min as first value at beginning

	for (int i=0; i<size; i++){
		min=i; //reset min
		for (int j=i; j<size; j++){
	//		cout << "j: " << j << endl;
			if (compare(table[min], table[j])){ //if min>table[j]
				min=j;
	//			cout << "min = " << min << endl;
			}
		}
		swap(table[min],table[i]);
	//	cout << "pass: " << i << endl;
	}
}

void InsertionSort(int table[], const int size){
	int min=0;//min here is value
	int j=0;
	
	for (int i=1; i<size; i++){
		min=table[i];
		j=i-1;
		while (j>=0 && compare(table[j], min)){
			table[j+1]=table[j];
			j--;
		} //end while
		table[j+1]=min;
	}
}

void InsertionSorty(int table[], const int size){
	int i,j,min;
	for(i=1; i<size+1; i++){
		j=i-1;
//		cout << "pass: " << i << endl;
		while(j>0 && compare(table[j-1],table[j])){
			swap(table[j-1],table[j]);
			j--;
//			cout << "invert" << " ";
		}
	}
}

void RadixSort(int a[], const int size){
	int b=32; //32-bit integer;
	int r=4; //radix

	int r_size=(1<<r);
	cout << "r_size: " << r_size << endl;
	r_size=16;

	int groups=(int)ceil((double)b/(double)r);
	int mask=r_size-1;

	int count[r_size];
	int pref[r_size];
	int t[size];
		
	for (int gi=0, shift=0; gi<groups; gi++, shift+=r){
		
		//reset and populate count[]
		for (int j=0; j<r_size; j++) count[j]=0;
		for (int i=0; i<size; i++) 
			count[ (a[i]>>shift)&mask ]++;

		//populate pref[[]
		pref[0]=0;
		for (int i=1; i<r_size; i++)
			pref[i] = pref[i-1]+count[i-1];

		//order a[] by cth group and put in target t[] array
		for (int i=0; i<size; i++)
			t[ pref[(a[i]>>shift)&mask]++ ] = a[i];

		//set a=t and redo for next group
		for (int j=0; j<size; j++) a[j]=t[j];
	
		cout << "gi: " << gi;
		print(a, size);
		print(count,r_size);
		print(pref,r_size);
	}
}

void QuickSort(int table[], int left, int right){
	int i=left, j=right;
	int pivot=table[(left+right)/2];

	//partition
	while(i<=j){
		while(table[i]<pivot) i++;
		while(table[j]>pivot) j--;

		if (i<=j){
			swap (table[i], table[j]);
			i++;
			j--;
		}
	};
	
	//recursion
	if(left<j) QuickSort(table, left, j);
	if(i<right) QuickSort(table, i, right);
}

void print(int table[], const int n){
	cout << "\n********** TABLE: *********\n";
	for (int i=0; i<n; i++){
		cout << table[i] << " ";
	}
	cout << "\n***************************\n";
}


int main(int argc, char* argv[]){
	cout << "Name of program: \n" << argv[0] << endl;
	cout << "Arguments are: \n";

	for (int n=1; n<argc; n++)
		cout << setw(2) << n << ": " << argv[n] << '\n';
	
	cout << "\n Input quantity: ";
	cin >> q;

	tab = new int [q];
	cout << "Input numbers for (Bubble) sorting:\n";
	for (int n=0; n<q; n++){
		cout << (n+1) << ": ";
		cin >> tab[n];
	}

    bool quit=false; int option;
    while(!quit){
	cout << "\n Options:" << endl
	     << "1. Bubble Sort" << endl
	     << "2. Bubble Sort Optimized" << endl
	     << "3. Selection Sort" << endl
             << "4. Insertion Sort" << endl
	     << "5. Radix Sort" << endl
	     << "6. Quick Sort" << endl
	     << "7. Self-populate array with random numbers" << endl
	     << "8. PRINT ARRAY" << endl
	     << "9. Quit" << endl
       	     << "What would you like to do today:";
	cin >> option;

	switch(option){
	case 1: cout << "BUBBLE SORT" << endl;
		BubbleSort(tab, q); // BubbleSort
		print(tab,q);
		break;
	case 2: cout << "BUBBLE SORT OPTIMIZED (with swap check)" << endl;
		BubbleSortOptimized(tab, q); // BubbleSort impln. w/ swap check
		print(tab,q);
		break;
	case 3: cout << "SELECTION SORT" << endl;
		SelectionSort(tab, q); // Selection Sort
		print(tab,q);
		break;
	case 4: cout << "INSERTION SORT" << endl;
		print(tab,q);
		InsertionSorty(tab, q); // Insertion Sort
		print(tab,q);
		break;
	case 5: cout << "RADIX SORT" << endl;
		print(tab,q);
		RadixSort(tab, q); // Insertion Sort
		print(tab,q);
		break;
	case 6: cout << "QUICK SORT" << endl;
		print(tab,q);
		QuickSort(tab,0,q);
		print(tab,q);
		break;

	case 7: cout << "how many nos? "; cin>>q;
		random(q);
		print(tab, q); 
		break;
	case 8: print(tab,q); break;
	case 9: quit=true; break;
	default: cout << "Illegal option!" << endl; break;
	}
    }

	for(int n=0; n<q; n++)
		cout << tab[n] << " ";
	cout << endl;

return 0;
}