Difference between revisions of "The Bean Counters"
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; | ||
+ | } | ||
− | = | + | 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
Email All
Projects
- sudoku - by Tian Debebe (CMU) not affiliated with Yankai whatsoever
- 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]; } }