The Bean Counters

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

1. Yankai Tian
2. Jay Ansin

 Email All

Projects

1. sudoku - by Tian Debebe (CMU) not affiliated with Yankai whatsoever
2. 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:

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:

Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total
 time   seconds   seconds    calls  Ts/call  Ts/call  name
 99.71      3.46     3.46                             void radixSort<float>(float*, int)
  0.29      3.47     0.01                             void quickSort<float>(float*, int, int)
  0.00      3.47     0.00     1091     0.00     0.00  void std::__move_median_first<__gnu_cxx::__normal_iterator<float*, std::vector<float, std::allocator<float> > > >(__gnu_cxx::__normal_iterator<float*, std::vector<float, std::allocator<float> > >, __gnu_cxx::__normal_iterator<float*, std::vector<float, std::allocator<float> > >, __gnu_cxx::__normal_iterator<float*, std::vector<float, std::allocator<float> > >)
  0.00      3.47     0.00      112     0.00     0.00  void std::vector<float, std::allocator<float> >::_M_insert_aux<float const&>(__gnu_cxx::__normal_iterator<float*, std::vector<float, std::allocator<float> > >, float const&&&)
  0.00      3.47     0.00       10     0.00     0.00  void std::__insertion_sort<__gnu_cxx::__normal_iterator<float*, std::vector<float, std::allocator<float> > > >(__gnu_cxx::__normal_iterator<float*, std::vector<float, std::allocator<float> > >, __gnu_cxx::__normal_iterator<float*, std::vector<float, std::allocator<float> > >)
  0.00      3.47     0.00       10     0.00     0.00  void std::__introsort_loop<__gnu_cxx::__normal_iterator<float*, std::vector<float, std::allocator<float> > >, int>(__gnu_cxx::__normal_iterator<float*, std::vector<float, std::allocator<float> > >, __gnu_cxx::__normal_iterator<float*, std::vector<float, std::allocator<float> > >, int)
  0.00      3.47     0.00        1     0.00     0.00  _GLOBAL__sub_I_main