Untitled
unknown
plain_text
2 years ago
16 kB
9
Indexable
Never
#include <iostream>
#include <fstream>
#include <string>
#include <chrono>
#include <vector>
#include <algorithm>
using namespace std;
class vector_sort
{
public:
static double BubbleSort(vector<int>& values)
{
auto begin = std::chrono::steady_clock::now();
for (size_t idx_i = 0; idx_i + 1 < values.size(); ++idx_i) {
for (size_t idx_j = 0; idx_j + 1 < values.size() - idx_i; ++idx_j) {
if (values[idx_j + 1] < values[idx_j]) {
swap(values[idx_j], values[idx_j + 1]);
}
}
}
auto end = std::chrono::steady_clock::now();
auto elapsed_ms = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
double b = elapsed_ms.count();
return b / 1000000;
}
static double ShakerSort(vector<int>& values)
{
auto begin = std::chrono::steady_clock::now();
if (values.empty()) {
return 0;
}
int left = 0;
int right = values.size() - 1;
while (left <= right) {
for (int i = right; i > left; --i) {
if (values[i - 1] > values[i]) {
swap(values[i - 1], values[i]);
}
}
++left;
for (int i = left; i < right; ++i) {
if (values[i] > values[i + 1]) {
swap(values[i], values[i + 1]);
}
}
--right;
}
auto end = std::chrono::steady_clock::now();
auto elapsed_ms = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
double b = elapsed_ms.count();
return b / 1000000;
}
static double CombSort(vector<int>& values)
{
const double factor = 1.247; // Фактор уменьшения
auto begin = std::chrono::steady_clock::now();
double step = values.size() - 1;
while (step >= 1) {
for (int i = 0; i + step < values.size(); ++i) {
if (values[i] > values[i + step]) {
swap(values[i], values[i + step]);
}
}
step /= factor;
}
// сортировка пузырьком
BubbleSort(values);
auto end = std::chrono::steady_clock::now();
auto elapsed_ms = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
double b = elapsed_ms.count();
return b / 1000000;
}
static double InsertionSort(vector<int>& values)
{
auto begin = std::chrono::steady_clock::now();
for (size_t i = 1; i < values.size(); ++i) {
int x = values[i];
size_t j = i;
while (j > 0 && values[j - 1] > x) {
values[j] = values[j - 1];
--j;
}
values[j] = x;
}
auto end = std::chrono::steady_clock::now();
auto elapsed_ms = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
double b = elapsed_ms.count();
return b / 1000000;
}
static double SelectionSort(vector<int>& values)
{
auto begin = std::chrono::steady_clock::now();
for (auto i = values.begin(); i != values.end(); ++i) {
auto first = i;
auto last = values.end();
if (first == last)
auto j = last;
auto smallest = first;
++first;
for (; first != last; ++first)
if (first < smallest)
smallest = first;
auto j = smallest;
swap(*i, *j);
}
auto end = std::chrono::steady_clock::now();
auto elapsed_ms = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
double b = elapsed_ms.count();
return b / 1000000;
}
static double HeapSort(vector<int>& values)
{
auto begin = std::chrono::steady_clock::now();
make_heap(values.begin(), values.end());
for (auto i = values.end(); i != values.begin(); --i) {
pop_heap(values.begin(), i);
}
auto end = std::chrono::steady_clock::now();
auto elapsed_ms = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
double b = elapsed_ms.count();
return b / 1000000;
}
private:
static void MergeSortImpl(vector<int>& values, vector<int>& buffer, int l, int r)
{
if (l < r) {
int m = (l + r) / 2;
MergeSortImpl(values, buffer, l, m);
MergeSortImpl(values, buffer, m + 1, r);
int k = l;
for (int i = l, j = m + 1; i <= m || j <= r; ) {
if (j > r || (i <= m && values[i] < values[j])) {
buffer[k] = values[i];
++i;
}
else {
buffer[k] = values[j];
++j;
}
++k;
}
for (int i = l; i <= r; ++i) {
values[i] = buffer[i];
}
}
}
public:
static double MergeSort(vector<int>& values)
{
auto begin = std::chrono::steady_clock::now();
if (!values.empty()) {
vector<int> buffer(values.size());
MergeSortImpl(values, buffer, 0, values.size() - 1);
}
auto end = std::chrono::steady_clock::now();
auto elapsed_ms = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
double b = elapsed_ms.count();
return b / 1000000;
}
private:
static int Partition(vector<int>& values, int l, int r)
{
int x = values[r];
int less = l;
for (int i = l; i < r; ++i) {
if (values[i] <= x) {
swap(values[i], values[less]);
++less;
}
}
swap(values[less], values[r]);
return less;
}
static void QuickSortImpl(vector<int>& values, int l, int r)
{
if (l < r) {
int q = Partition(values, l, r);
QuickSortImpl(values, l, q - 1);
QuickSortImpl(values, q + 1, r);
}
}
public:
static double QuickSort(vector<int>& values)
{
auto begin = std::chrono::steady_clock::now();
if (!values.empty()) {
QuickSortImpl(values, 0, values.size() - 1);
}
auto end = std::chrono::steady_clock::now();
auto elapsed_ms = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
double b = elapsed_ms.count();
return b / 1000000;
}
};
int main()
{
setlocale(LC_ALL, "Russian");
vector<int> rand_s;
vector<int> rand_m;
vector<int> rand_b;
ifstream f1("C:/Users/dazhukov/Desktop/Сортировка тест файлы/Случ-м.txt");
for (int i = 0; i < 100; i++) {
string temp;
getline(f1, temp);
rand_s.push_back(stoi(temp));
}
ifstream f2("C:/Users/dazhukov/Desktop/Сортировка тест файлы/Случ-c.txt");
for (int i = 0; i < 1000; i++) {
string temp;
getline(f2, temp);
rand_m.push_back(stoi(temp));
}
ifstream f3("C:/Users/dazhukov/Desktop/Сортировка тест файлы/Случ-б.txt");
for (int i = 0; i < 10000; i++) {
string temp;
getline(f3, temp);
rand_b.push_back(stoi(temp));
}
vector<int> rand_s_temp = rand_s;
vector<int> rand_m_temp = rand_m;
vector<int> rand_b_temp = rand_b;
vector<int> sort_s;
vector<int> sort_m;
vector<int> sort_b;
ifstream f4("C:/Users/dazhukov/Desktop/Сортировка тест файлы/Упор-м.txt");
for (int i = 0; i < 100; i++) {
string temp;
getline(f4, temp);
sort_s.push_back(stoi(temp));
}
ifstream f5("C:/Users/dazhukov/Desktop/Сортировка тест файлы/Упор-c.txt");
for (int i = 0; i < 1000; i++) {
string temp;
getline(f5, temp);
sort_m.push_back(stoi(temp));
}
ifstream f6("C:/Users/dazhukov/Desktop/Сортировка тест файлы/Упор-б.txt");
for (int i = 0; i < 10000; i++) {
string temp;
getline(f6, temp);
sort_b.push_back(stoi(temp));
}
vector<int> unsort_s;
vector<int> unsort_m;
vector<int> unsort_b;
ifstream f7("C:/Users/dazhukov/Desktop/Сортировка тест файлы/Антиупор-м.txt");
for (int i = 0; i < 100; i++) {
string temp;
getline(f7, temp);
unsort_s.push_back(stoi(temp));
}
ifstream f8("C:/Users/dazhukov/Desktop/Сортировка тест файлы/Антиупор-c.txt");
for (int i = 0; i < 1000; i++) {
string temp;
getline(f8, temp);
unsort_m.push_back(stoi(temp));
}
ifstream f9("C:/Users/dazhukov/Desktop/Сортировка тест файлы/Антиупор-б.txt");
for (int i = 0; i < 10000; i++) {
string temp;
getline(f9, temp);
unsort_b.push_back(stoi(temp));
}
const vector<int> unsort_s_temp = unsort_s;
const vector<int> unsort_m_temp = unsort_m;
const vector<int> unsort_b_temp = unsort_b;
const vector<int> rand_s_temp = rand_s;
const vector<int> rand_m_temp = rand_m;
const vector<int> rand_b_temp = rand_b;
// В миллисекундах
double sort_time[8][3]{
vector_sort::BubbleSort(sort_s), vector_sort::BubbleSort(sort_m), vector_sort::BubbleSort(sort_b),
vector_sort::ShakerSort(sort_s), vector_sort::ShakerSort(sort_m), vector_sort::ShakerSort(sort_b),
vector_sort::CombSort(sort_s), vector_sort::CombSort(sort_m), vector_sort::CombSort(sort_b),
vector_sort::InsertionSort(sort_s), vector_sort::InsertionSort(sort_m), vector_sort::InsertionSort(sort_b),
vector_sort::SelectionSort(sort_s), vector_sort::SelectionSort(sort_m), vector_sort::SelectionSort(sort_b),
vector_sort::HeapSort(sort_s), vector_sort::HeapSort(sort_m), vector_sort::HeapSort(sort_b),
vector_sort::MergeSort(sort_s), vector_sort::MergeSort(sort_m), vector_sort::MergeSort(sort_b),
vector_sort::QuickSort(sort_s), vector_sort::QuickSort(sort_m), //vector_sort::QuickSort(sort_b)
};
double unsort_time[8][3]{
vector_sort::BubbleSort(unsort_s), vector_sort::BubbleSort(unsort_m), vector_sort::BubbleSort(unsort_b),
vector_sort::ShakerSort(unsort_s), vector_sort::ShakerSort(unsort_m), vector_sort::ShakerSort(unsort_b),
vector_sort::CombSort(unsort_s), vector_sort::CombSort(unsort_m), vector_sort::CombSort(unsort_b),
vector_sort::InsertionSort(unsort_s), vector_sort::InsertionSort(unsort_m), vector_sort::InsertionSort(unsort_b),
vector_sort::SelectionSort(unsort_s), vector_sort::SelectionSort(unsort_m), vector_sort::SelectionSort(unsort_b),
vector_sort::HeapSort(unsort_s), vector_sort::HeapSort(unsort_m), vector_sort::HeapSort(unsort_b),
vector_sort::MergeSort(unsort_s), vector_sort::MergeSort(unsort_m), vector_sort::MergeSort(unsort_b),
vector_sort::QuickSort(unsort_s), vector_sort::QuickSort(unsort_m), //vector_sort::QuickSort(unsort_b)
};
for (int i = 0; i < 8; i++) {
for (int j = 0; j < 3; j++) {
if (i == 0) {
if (j == 0) {
unsort_time[i][j] = vector_sort::BubbleSort(unsort_s);
rand_time[i][j] = vector_sort::BubbleSort(unsort_s);
}
if (j == 1) {
unsort_time[i][j] = vector_sort::BubbleSort(unsort_m);
rand_time[i][j] = vector_sort::BubbleSort(rand_m);
}
if (j == 2) {
unsort_time[i][j] = vector_sort::BubbleSort(unsort_b);
rand_time[i][j] = vector_sort::BubbleSort(rand_b);
}
unsort_s = unsort_s_temp;
unsort_m = unsort_m_temp;
unsort_b = unsort_b_temp;
}
if (i == 1) {
if (j == 0) {
unsort_time[i][j] = vector_sort::ShakerSort(unsort_s);
rand_time[i][j] =
}
if (j == 1) {
unsort_time[i][j] = vector_sort::ShakerSort(unsort_m);
rand_time[i][j] =
}
if (j == 2) {
unsort_time[i][j] = vector_sort::ShakerSort(unsort_b);
rand_time[i][j] =
}
unsort_s = unsort_s_temp;
unsort_m = unsort_m_temp;
unsort_b = unsort_b_temp;
}
if (i == 2) {
if (j == 0) {
unsort_time[i][j] = vector_sort::CombSort(unsort_s);
rand_time[i][j] =
}
if (j == 1) {
unsort_time[i][j] = vector_sort::CombSort(unsort_m);
rand_time[i][j] =
}
if (j == 2) {
unsort_time[i][j] = vector_sort::CombSort(unsort_b);
rand_time[i][j] =
}
unsort_s = unsort_s_temp;
unsort_m = unsort_m_temp;
unsort_b = unsort_b_temp;
}
if (i == 3) {
if (j == 0) {
unsort_time[i][j] = vector_sort::InsertionSort(unsort_s);
rand_time[i][j] =
}
if (j == 1) {
unsort_time[i][j] = vector_sort::InsertionSort(unsort_m);
rand_time[i][j] =
}
if (j == 2) {
unsort_time[i][j] = vector_sort::InsertionSort(unsort_b);
rand_time[i][j] =
}
unsort_s = unsort_s_temp;
unsort_m = unsort_m_temp;
unsort_b = unsort_b_temp;
}
if (i == 4) {
if (j == 0) {
unsort_time[i][j] = vector_sort::SelectionSort(unsort_s);
rand_time[i][j] =
}
if (j == 1) {
unsort_time[i][j] = vector_sort::SelectionSort(unsort_m);
rand_time[i][j] =
}
if (j == 2) {
unsort_time[i][j] = vector_sort::SelectionSort(unsort_b);
rand_time[i][j] =
}
unsort_s = unsort_s_temp;
unsort_m = unsort_m_temp;
unsort_b = unsort_b_temp;
}
if (i == 5) {
if (j == 0) {
unsort_time[i][j] = vector_sort::HeapSort(unsort_s);
rand_time[i][j] =
}
if (j == 1) {
unsort_time[i][j] = vector_sort::HeapSort(unsort_m);
rand_time[i][j] =
}
if (j == 2) {
unsort_time[i][j] = vector_sort::HeapSort(unsort_b);
rand_time[i][j] =
}
unsort_s = unsort_s_temp;
unsort_m = unsort_m_temp;
unsort_b = unsort_b_temp;
}
if (i == 6) {
if (j == 0) {
unsort_time[i][j] = vector_sort::MergeSort(unsort_s);
rand_time[i][j] =
}
if (j == 1) {
unsort_time[i][j] = vector_sort::MergeSort(unsort_m);
rand_time[i][j] =
}
if (j == 2) {
unsort_time[i][j] = vector_sort::MergeSort(unsort_b);
rand_time[i][j] =
}
unsort_s = unsort_s_temp;
unsort_m = unsort_m_temp;
unsort_b = unsort_b_temp;
}
if (i == 7) {
if (j == 0) {
unsort_time[i][j] = vector_sort::QuickSort(unsort_s);
rand_time[i][j] =
}
if (j == 1) {
unsort_time[i][j] = vector_sort::QuickSort(unsort_m);
rand_time[i][j] =
}
if (j == 2) {
unsort_time[i][j] = -1; //vector_sort::QuickSort(unsort_b)
rand_time[i][j] = -1;
}
unsort_s = unsort_s_temp;
unsort_m = unsort_m_temp;
unsort_b = unsort_b_temp;
}
}
}
double rand_time[8][3]{
vector_sort::BubbleSort(rand_s), vector_sort::BubbleSort(rand_m), vector_sort::BubbleSort(rand_b),
vector_sort::ShakerSort(rand_s), vector_sort::ShakerSort(rand_m), vector_sort::ShakerSort(rand_b),
vector_sort::CombSort(rand_s), vector_sort::CombSort(rand_m), vector_sort::CombSort(rand_b),
vector_sort::InsertionSort(rand_s), vector_sort::InsertionSort(rand_m), vector_sort::InsertionSort(rand_b),
vector_sort::SelectionSort(rand_s), vector_sort::SelectionSort(rand_m), vector_sort::SelectionSort(rand_b),
vector_sort::HeapSort(rand_s), vector_sort::HeapSort(rand_m), vector_sort::HeapSort(rand_b),
vector_sort::MergeSort(rand_s), vector_sort::MergeSort(rand_m), vector_sort::MergeSort(rand_b),
vector_sort::QuickSort(rand_s), vector_sort::QuickSort(rand_m), //vector_sort::QuickSort(rand_b)
};
while (true)
{
int b;
system("cls");
cout << "Здравствуйте, какую таблицу вы хотите? \n1 - Конкретная сортировка, 2 - Все сортировки" << endl;
cout << ">> "; cin >> b;
if (b == 1) {
system("cls");
cout << "1 - Заново, \n 2 - Пузырьковая сортировка \n 3 - Шейкерная сортировка \n";
cout << "4 - Комбинированная сортировка\n 5 - Сортировка вставками\n 6 - Сортировка выбором\n";
cout << "7 - Пирамидальная сортировка\n 8 - Сортировка слиянием \n 9 - Быстрая сортировка\n";
cout << ">> "; cin >> b;
if (b == 1) continue;
else if (b == 2) {
}
else if (b == 3) {
}
else if (b == 4) {
}
else if (b == 5) {
}
else if (b == 6) {
}
else if (b == 7) {
}
else if (b == 8) {
}
else if (b == 9) {
}
else {
cout << "Неверный ввод";
continue;
}
}
}
return 0;
}