Changes
Jump to:
navigation
,
search
← Older edit
The Bean Counters
7,004 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 =
== A1: Select and Assess ==
There wasn't a project source code for this. Everything was written by yours truly. etc. etc. etc. The 10 algorithms tested are:
=== Source Code ===
===== 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;
}
}
}
=== Results ===
==== Flat Profile ====
==== Call Graph ====
==== Clustered Column Chart ====
== A2: Parallelize ==
=== Source Code ===
===== bubble sort =====
===== selection sort =====
===== insertion sort =====
=== Results ===
==== Visual Profiler ====
==== Parallel NSight ====
==== Comparison ====
== A3: Optimize ==
=== Source Code ===
===== bubble sort =====
===== selection sort =====
===== insertion sort =====
=== Results ===
==== Visual Profiler ====
==== Parallel NSight ====
==== Comparison ====
Victoriouswaffles
110
edits
Navigation menu
Personal tools
Log in
Namespaces
Page
Discussion
Variants
Views
Read
View source
View history
More
Search
Navigation
CDOT
SICT AR Meeting Area
People
get involved with CDOT
as a Student
as an Open Source Community Member
as a Company
courses
BTC640
BTH740
BTP300
DPI908
DPS901
DPS905
DPS909
DPS911
DPS914
DPS915
DPS924
DPS931
EAC234
ECL500
GAM531
GAM666
GAM670
GPU610
LUX Program
MAP524
OOP344
OPS102
OPS235
OPS245
OPS335
OPS345
OPS435
OPS445
OPS535
OPS635
OSD600
OSD700
OSL640
OSL740
OSL840
Real World Mozilla
RHT524
SBR600
SEC520
SPO600
SRT210
ULI101
course projects
Course Project List
Potential Course Projects
Contrib Opportunities
links
CDOT
Planet CDOT
FSOSS
Tools
Special pages