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
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:
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;
}
}
}