Коды основных функций / [Код основных функций] Лаб. 1
.pdf
[Код основных функций] Лабораторная работа №1. Сортировка
//Get the current time.
//This function should be used only for measuring time
//(first call, algorithm, second call; then the difference between the values) double getProcTime() {
#if defined(_WIN32) // If Windows:
FILETIME createTime, exitTime, kernelTime, userTime;
if (GetProcessTimes(GetCurrentProcess(), &createTime, &exitTime, &kernelTime, &userTime) != -1)
return (ULARGE_INTEGER { {userTime.dwLowDateTime, userTime.dwHighDateTime } }).QuadPart / 10000000.L;
return 0;
#else // If Linux or MacOS:
return double(clock()) / CLOCKS_PER_SEC; #endif
}
//Standard sort
template <class T = int>
void standardSort(std::vector<T> & vec) { std::sort(vec.begin(), vec.end());
}
// Bubble sort
template <class T = int>
void bubbleSort(std::vector<T> & vec) {
for (int i = 0, endIdx = vec.size() - 1; i < endIdx; ++i) for (int j = 0; j < endIdx; ++j)
if (vec[j] > vec[j + 1]) std::swap(vec[j], vec[j + 1]);
}
// Shaker sort
template <class T = int>
void cocktailSort(std::vector<T> & vec) { int left = 0, right = vec.size() - 1; while (left <= right) {
for (int i = left; i < right; ++i) if (vec[i] > vec[i + 1])
std::swap(vec[i], vec[i + 1]); --right;
for (int i = right; i > left; --i) if (vec[i - 1] > vec[i])
std::swap(vec[i - 1], vec[i]); ++left;
}
}
//Selection sort template <class T = int>
void selectionSort(std::vector<T> & vec) {
for (int i = 0, len = vec.size(), endIdx = len - 1; i < endIdx; ++i) { int min = i;
for (int j = i + 1; j < len; ++j) if (vec[j] < vec[min]) min = j;
if (min != i) std::swap(vec[i], vec[min]);
}
}
//Insertion sort
template <class T = int>
void insertionSort(std::vector<T> & vec) {
for (int i = 1, len = vec.size(); i < len; ++i) { T itemToInsert(vec[i]);
int j = i - 1;
for (; j >= 0 && vec[j] > itemToInsert; --j) vec[j + 1] = vec[j];
vec[j + 1] = itemToInsert;
}
}
// Shell sort
template <class T = int>
void shellSort(std::vector<T> & vec) {
for (int len = vec.size(), step = len >> 1; step > 0; step >>= 1) for (int i = step; i < len; ++i)
for (int j = i - step; j >= 0 && vec[j] > vec[j + step]; j -= step) std::swap(vec[j], vec[j + step]);
}
// Hoare iterative sort template <class T = int>
void hoareIterativeSort(std::vector<T> & vec) { std::stack<std::pair<int, int>> total; total.push(std::make_pair<int, int>(+0, vec.size() - 1)); while (!total.empty()) {
auto p = total.top(); total.pop();
int left = p.first, right = p.second; while (left < right) {
int i = left, j = right;
T middle = vec[((right - left) >> 1) + left]; while (i < j) {
while (vec[i] < middle) ++i; while (middle < vec[j]) --j;
if (i <= j) std::swap(vec[i++], vec[j--]);
}
if (i < right) total.push(std::make_pair<int, int>(+i, +right)); right = j;
}
}
}
// Merge sort
template <class T = int>
void mergeParts(std::vector<T> & vec, std::vector<T> & temp, int i, int current) { int j = i + current, n = vec.size();
int n1 = std::min(j, n), n2 = std::min(j + current, n), k = i;
while (i < n1 && j < n2) temp[k++] = (vec[i] <= vec[j]) ? vec[i++] : vec[j++]; while (i < n1) temp[k++] = vec[i++];
while (j < n2) temp[k++] = vec[j++];
}
template <class T = int>
void mergeSort(std::vector<T> & vec) { int len = vec.size();
std::vector<T> temp(len);
for (int current = 1, next = current << 1; current < len; current = next, next <<= 1)
{
for (int i = 0; i < len; i += next) mergeParts(vec, temp, i, current);
current = next, next <<= 1; for (int i = 0; i < len; i += next)
mergeParts(temp, vec, i, current);
}
}
Пройденное тестирование:
1.Пустой массив.
2.Массив из одного элемента.
3.Массив большого размера с единственным уникальным элементом.
4.Сортированный по убыванию большой массив.
5.Простые тесты (случайные массивы, неповторяющиеся элементы). Реализуется созданием массива с последовательными значениями и случайной перестановкой его элементов.
6.Сложные тесты (случайные массивы, повторяющиеся элементы).
Проверка осуществляется сравнением получившегося результата и результата стандартной сортировки C++ std::sort.