Difference between revisions of "The Bean Counters"

From CDOT Wiki
Jump to: navigation, search
Line 54: Line 54:
  
 
===== insertion sort =====
 
===== 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;
 +
}
  
===== merge sort =====
+
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 =====
 
===== heap sort =====

Revision as of 15:55, 2 April 2018


GPU610/DPS915 | Student List | Group and Project Index | Student Resources | Glossary

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

  1. Yankai Tian
  2. Jay Ansin
 Email All


Projects

  1. sudoku - by Tian Debebe (CMU) not affiliated with Yankai whatsoever
  2. sorting algorithms - Alex Allain cprogramming.com, 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
quick sort
counting sort
radix sort
bucket sort
shell sort

Parallelize

bubble sort
selection sort
insertion sort

Optimize

bubble sort
selection sort
insertion sort