Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstdlib>
- #include <iostream>
- #include <chrono>
- using namespace std;
- using namespace std::chrono;
- // Алгоритм шейкерной сортировки
- void CocktailSort(int arr[], int n) // Шейкерная сортировка, которая принимает в качестве параметров массива и его размер
- {
- bool swapped = true; // Инициализация булевой переменной swapped значением true
- int start = 0; // Инициализация целочисленной переменной start нулём
- int end = n - 1; // Инициализация целочисленной переменной end значением n - 1
- while (swapped) { // Пока swapped = true
- // Сброс swapped, так как предыдущая итерация может быть истинной
- swapped = false; // Присвоение переменной swapped значения false
- // Цикл слево направо такой же, как пузырьковая сортирвка
- for (int i = start; i < end; ++i) {
- if (arr[i] > arr[i + 1]) {
- swap(arr[i], arr[i + 1]);
- swapped = true;
- }
- }
- // Если ничего не было перемещено, то массив отсортирован
- if (!swapped)
- break;
- // В противном случае сбросить swapped
- swapped = false;
- // Переместить конечную точку на единицу назад потому, что элемент в конце находится на правильном месте
- --end;
- // Цикл справа налево такой же
- for (int i = end - 1; i >= start; --i) {
- if (arr[i] > arr[i + 1]) {
- swap(arr[i], arr[i + 1]);
- swapped = true;
- }
- }
- ++start; // Инкрементирование переменной start
- }
- }
- // Быстрая сортировка
- void QuickSort(int* arr, int first, int last) // Быстрая сортировка, которая принимает в качестве параметров указатель на массив,
- // первого и последнего элемента
- {
- int mid, count; // Объявление переменных mid, count
- int f = first, l = last; // Инициализация переменных f и l
- mid = arr[(f + l) / 2]; //вычисление опорного элемента
- do // Начало цикла
- {
- while (arr[f] < mid) f++; // Пока первый элемент меньше опорного инкрементирование f
- while (arr[l] > mid) l--; // Пока последний элемент больше опорного декрементирование l
- if (f <= l) //перестановка элементов
- {
- count = arr[f]; // Присвоение переменной count значения первого элемента
- arr[f] = arr[l]; // Присвоение первому элементу массива значения последнего элемента
- arr[l] = count; // Присвоение последнему элементу массива значения переменной count
- f++; // Инкрементирование f
- l--; // Декрементирование l
- }
- } while (f < l); // Пока первый элемент меньше последнего
- if (first < l) QuickSort(arr, first, l); // Выполнить рекурсивное упорядочивание левой части нужно в том случае, если выполняется условие L<last.
- // Для правой части условие аналогично: first < R.
- if (f < last) QuickSort(arr, f, last);
- }
- void Randomazer(int x[], int n) // Рандомайзер, который принимает в качестве параметров массив и его размер
- {
- for (int i = 0; i < n; i++) // Цикл по переменно i в диапазоне от 0 до n не включительно
- {
- x[i] = rand() % 10; // Заполненние массива случайными числами до 10
- }
- }
- void Print(int x[], int n) // Функция, выводящая массив на экран, которая принимает в качестве параметров массив и его размер
- {
- for (int i = 0; i < n; ++i) // Цикл по переменно i в диапазоне от 0 до n не включительно
- {
- cout << x[i] << " "; // Вывод i-го элемента и пробела
- }
- cout << endl; // Перевод строки
- }
- int main() // Основной алгоритм
- {
- setlocale(0, ""); // Установка русского языка в консоле
- int n; // Объявление переменной n
- cout << "Размер массива: 10 или 100?" << endl; // Вывод сообщения "Размер массива: 10 или 100?" с переводом строки
- cin >> n; // Ввод значения переменной n с клавиатуры
- int fisrt = 0, last = n - 1; // Инициализация переменных fisrt и last
- auto* x = new int[n]; // Создание целочисленного динамического массива размера n
- //Randomazer(x, n); // Вызов функции Randomazer с параметрами x и n
- for (int i = 0; i < n; i++) // Цикл по переменно i в диапазоне от 0 до n не включительно
- {
- int el; // Объявление переменной el
- cout << "Введите элемент #" << i + 1 << ": "; cin >> el; // Вывод сообщения "Введите элемент #" i + 1 и ввод значения переменной el с клавиатуры
- x[i] = el; // Присвоение i-му элементу массива значения el
- }
- cout << "Ваш массив" << endl; // Вывод сообщения "Ваш массив" с переводом строки
- Print(x, n); // Вызов функции Print с параметрами x и n
- auto start = high_resolution_clock::now();
- //CocktailSort(x, n); // Вызов функции CocktailSort с параметрами x и n
- QuickSort(x, fisrt, last); // Вызов функции QuickSort с параметрами x, fisrt и last
- auto stop = high_resolution_clock::now();
- auto duration = duration_cast<milliseconds>(stop - start);
- cout << "Время выполнения: " << duration.count() << " milliseconds" << endl;
- cout << "Отсортированный массив" << endl; // Вывод сообщения "Очищенный массив" с переводом строки
- Print(x, n); // Вызов функции Print с параметрами x и n
- delete[]x; // Удаление массива x
- system("pause"); // Пауза для просмотра результата
- return 0; // Возврат нуля - индикатор корректности завершения программы
- }
Add Comment
Please, Sign In to add comment