110
edits
Changes
no edit summary
=Progress=
== 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 =====
===== 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; } } }
