View source for The Bean Counters

{{GPU610/DPS915 Index | 20181}}

= The Bean Counters =
''Beans are a cheap commodity, so to count them is a rather silly thing to do. A "bean counter" is one who nitpicks over small things in order to save costs.''

== Team Members ==
# [mailto:ytian38@myseneca.ca?/subject=GPU610 Yankai Tian]
# [mailto:cansin@myseneca.ca?/subject=GPU610 Jay Ansin]

  [mailto:ytian38@myseneca.ca,cansin@myseneca.ca?/subject=GPU610 Email All]


== Projects ==
# sudoku - [http://www.andrew.cmu.edu/user/astian/ by Tian Debebe (CMU)] ''not affiliated with Yankai whatsoever''
# '''sorting algorithms''' - [http://www.cprogramming.com/tutorial/computersciencetheory/sortcomp.html Alex Allain cprogramming.com], [https://www.toptal.com/developers/sorting-algorithms Animations]



= Progress =

== Select and Assess ==
There wasn't a project source code for this. Everything was written by yours truly. etc. etc. etc.

=== Sorting Algorithms ===
The 10 algorithms tested are: 
===== bubble sort =====
 template<typename T>
 inline void bubbleSort(T * array, int size) {
 	for (int i = 0; i < size; i++) 	{
 		for (int j = 0; j < size - 1; j++) {
 			if (array[j] > array[j + 1]) {
 				T swap = array[j + 1];
 				array[j + 1] = array[j];
 				array[j] = swap;
 			}
 		}
 	}
 }

===== selection sort =====
 template<typename T>
 inline void selectionSort(T * array, int size) {
 	for (int i = 0; i < size; i++) {
 		int min = i;
 		for (int j = i; j < size; j++) {
 			if (array[min] > array[j])
 				min = j;
 		}
 		T temp = array[i];
 		array[i] = array[min];
 		array[min] = temp;
 	}
 }

===== insertion sort =====
 template<typename T>
 inline void insertionSort(T * array, int size) {
 	T curr;
 	int j;
 	for (int i = 0; i < size; i++) {
 		curr = array[i];
 		for (j = i; j > 0 && array[j - 1] > curr; j--) {
 			array[j] = array[j - 1];
  		}
 		array[j] = curr;
 	}
 }

===== merge sort =====
 template<typename T>
 inline void mergeSort(T * array, int size) {
 	T * temp = new T[size];
 	mergeSort(array, temp, 0, size - 1);
 	delete[] temp;
 }

 template<typename T>
 inline void mergeSort(T * array, T * temp, int start, int end) {
 	if (start < end) {
 		int mid = (start + end) / 2;
 		mergeSort(array, temp, start, mid);
 		mergeSort(array, temp, mid + 1, end);
 		merge(array, temp, start, mid + 1, end);
 	}
 }

 template<typename T>
 inline void merge(T * array, T * temp, int startA, int startB, int endB) {
 	int aptr = startA;
 	int bptr = startB;
 	int idx = startA;
 	while (aptr < startB && bptr < endB + 1) {
 		if (array[aptr] < array[bptr]) {
 			temp[idx] = array[aptr];
 			idx++;
 			aptr++;
 		}
 		else {
 			temp[idx++] = array[bptr];
 			bptr++;
 		}
 	}
 	while (aptr<startB) {
 		temp[idx] = array[aptr];
 		idx++;
 		aptr++;
 	}
 	while (bptr < endB + 1) {
 		temp[idx++] = array[bptr];
 		bptr++;
 	}
 
 	for (int i = startA; i <= endB; i++) {
 		array[i] = temp[i];
 	}
 }

===== heap sort =====
 template<typename T>
 inline void heapSort(T * array, int size) {
 	for (int i = size / 2 - 1; i >= 0; i--) {
 		heapify(array, size, i);
 	}
 	for (int i = size - 1; i >= 0; i--) {
 		std::swap(array[0], array[i]);
 		heapify(array, i, 0);
 	}
 }

 template <typename T> 
 void heapify(T * array, int size, int i) {
 	int largest = i;
 	int left = 2 * i + 1;
 	int right = 2 * i + 2;
 	if (left < size && array[left] > array[largest])
 		largest = left;
 
 	if (right < size && array[right] > array[largest])
 		largest = right;
 
 	if (largest != i) {
 		std::swap(array[i], array[largest]);
 		heapify(array, size, largest);
 	}
 }

===== quick sort =====
 template<typename T>
 inline void quickSort(T * array, int size) {
 	quickSort(array, 0, size - 1);
 }

 template<typename T>
 inline void quickSort(T * array, int left, int right) {
 	if (right - left <= 3) {
 		insertionSort(array, left, right);
 	}
 	else {
 		int mid = (left + right) / 2;
 		std::swap(array[right], array[mid]);
 		int pivotpt = right; 
 		int i = left;
 		int j = right - 1;
 		T pivot = array[pivotpt];
 		while (i<j) {
 			while (i< right - 1 && array[i]<pivot) i++;
 			while (j > 0 && array[j]>pivot) j--;
  			if (i<j)
 				std::swap(array[i++], array[j--]);
 		}
 		if (i == j && array[i] < array[pivotpt])
 			i++;
 		std::swap(array[i], array[pivotpt]);
 		quickSort(array, left, i - 1);
 		quickSort(array, i + 1, right);
 	}
 }

===== counting sort =====
 template<typename T> 
 inline void countingSort(T * array, int size, int RANGE) {
 	T output[size];
 	int count[RANGE + 1];
 	std::memset(count, 0, sizeof(count));
 
 	for (int i = 0; array[i]; ++i) {
 		++count[(int)array[i]];
 	}
 
 	for (int i = 1; i <= RANGE; ++i) {
 		count[i] += count[i-1];
 	}
 
 	for (int i = 0; array[i]; ++i) {
 		output[(int)count[(int)array[i]] - 1] = array[i];
 		--count[(int)array[i]];
 	}
 
 	for (int i = 0; i < size; i++) {
 		array[i] = output[i];
 	}
 } 

===== radix sort =====
 template<typename T>
 inline void radixSort(T * array, int size) {
 	T maxNumber = array[0];
 	for (int i = 1; i < size; i++) {
 		if (array[i] > maxNumber)
 			maxNumber = array[i];
 	}
 
 	T exp = 1;
 	T * temp = new T[size];
 	while (maxNumber / exp > 0) {
 		T decimalBucket[10] = { 0 };
 		
 		for (int i = 0; i < size; i++)
 			decimalBucket[(int)array[i] / (int)exp % 10]++;
 
 		for (int i = 1; i < 10; i++)
 			decimalBucket[i] += decimalBucket[i - 1];
 
 		for (int i = size - 1; i >= 0; i--)
 			temp[(int)--decimalBucket[(int)array[i] / (int)exp % 10]] = array[i];
 
 		for (int i = 0; i < size; i++)
 			array[i] = temp[i];
 		
 		exp *= 10;
 	}
 } 

===== bucket sort =====
 template<typename T>
 inline void bucketSort(T * array, int size, int bucketSize) {
 	std::vector<T> buckets[bucketSize];
 	T max = getMax(array, size);
 	int divider = std::ceil(T(max + 1) / bucketSize);
 
 	for (int i = 0; i < size; i++) {
 		int j = floor(array[i] / divider);
 		buckets[j].push_back(array[i]);
 	}
 
 	for (int i = 0; i < bucketSize; i++) {
 		sort(buckets[i].begin(), buckets[i].end());
 	}
 
 	int k = 0;
 	for (int i = 0; i < bucketSize; i++) {
 		for (int j = 0; j < buckets[i].size(); j++) {
 			array[k++] = buckets[i][j];
 		}
 	}
 }

===== shell sort =====
 template <typename T> 
 void shellSort(T * array, int size) {
 	T temp;
 	for (int gap = size / 2; gap > 0; gap /= 2) {
 		for (int i = gap; i < size; i += 1) {
 			temp = array[i];
 			int j;
 			for (j = i; j >= gap && array[j - gap] > temp; j -= gap) {
 				array[j] = array[j - gap];
 			}
 			array[j] = temp;
 		}
 	}
 }



== Parallelize ==

===== bubble sort =====

===== selection sort =====

===== insertion sort =====




== Optimize ==

===== bubble sort =====

===== selection sort =====

===== insertion sort =====