|
|
| (32 intermediate revisions by 2 users not shown) |
| Line 1: |
Line 1: |
| − | {{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 =====
| |
