Open main menu

CDOT Wiki β

Changes

The Bean Counters

3,250 bytes removed, 11:05, 9 April 2018
Blanked the page
{{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 =====
 
 
===== quick sort =====
 
 
===== counting sort =====
 
 
===== radix sort =====
 
 
===== bucket sort =====
 
 
===== shell sort =====
 
 
 
 
== Parallelize ==
 
===== bubble sort =====
 
===== selection sort =====
 
===== insertion sort =====
 
 
 
 
== Optimize ==
 
===== bubble sort =====
 
===== selection sort =====
 
===== insertion sort =====