Алгоритмы сортировки

ГУАП

КАФЕДРА № 43

ОТЧЕТ
ЗАЩИЩЕН С ОЦЕНКОЙ

ПРЕПОДАВАТЕЛЬ

РАБОТУ ВЫПОЛНИЛ

Санкт-Петербург 2023

Цель работы.

Целью работы является изучение алгоритмов внутренней сортировки и получение практических навыков их использования, и анализа их сложности.
Вариант 10.

Листинг программы:

#include <iostream>
#include <locale.h>
#include <algorithm>
#include <cstring>
#include <set>

using namespace std;

const int SIZE = 1000;

void fillRandomArray(int arr[], int n) // Заполнение массива псевдослучайными значениями от 0 до 10000
{
   for (int i = 0; i < n; i++) {
       arr[i] = rand() % 10000;
   }
   cout << "\n Массив заполнен случайными значениями!" << endl;
}

void putArray(int arr[], int n) // Заполнение массива через консоль
{
   cout << "Введите " << n << " элементов через пробел: ";
   for (int i = 0; i < n; i++)cin >> arr[i];

   cout << "\n Массив заполнен." << endl;
}

void putSingleArrayElement(int arr[], int &n) // Вставка элемента
{
   int data, index;
   cout << "\n Введите индекс, под которым будет вставлен новый элемент: ";
   cin >> index;
   cout << "\n Введите значение элемента, которое хотите добавить: ";
   cin >> data;
   if (index < n && index >= 0) {
       for (int i = n; i > index; i--) {
           arr[i] = arr[i - 1];
       }
       n--;
   } else
       cout << "\n Недопустимый индекс вставляемого элемента!" << endl;
   arr[index] = data;
}

void removeElement(int arr[], int &n) // Удаление элемента по индексу в массиве
{
   int index; // индекс, по которому будем удалять
   cout << "\n Введите индекс элемента, который хотите удалить: ";
   cin >> index; // запрашиваем индекс

   // Проверка, есть ли такой индекс, в нашем массиве, не выходим ли мы за приделы.
   if (index >= n || index < 0) {
       cout << "\n Элемента с таким индексом нет!" << endl;
       return;
   }

   for (int i = index; i < n - 1; i++) { // Проходим по всем элементам начиная от индекса, до конца массива
       arr[i] = arr[i + 1]; // Смещаем элементы
   }
   n--; // Уменьшаем размер нашего массива

}

void uniqueCount(int arr[], int n) {
   set<int> nums; // Объявляем наш set

   for (int i = 0; i < n; ++i) nums.insert(arr[i]); // Добавляем в set каждый элемент

   cout << "Кол-во уникальных значений в массиве: " << nums.size() << endl; // Выводим размер нашего set
}

void printArray(int arr[], int n) // Вывод массива в консоль
{
   for (int i = 0; i < n; i++) { // Проходим по каждому элементу
       cout << arr[i] << " "; // Выводим его в консоль, добавляя пробел
   }
   cout << endl; // Добавляем отступ, чтобы отделить наш массив от остального текста
}

void sort(int arr[], int n) // Сортировка массива по возрастанию методом подсчета
{
   int numOfCompare = 0;
   int numOfReshuffle = 0;

   int max = arr[0];

   for (int i = 1; i < n; ++i) {
       numOfCompare++;
       if (arr[i] > max) max = arr[i];
   }

   int *c = (int *) malloc((max + 1) * sizeof(*arr));
   memset(c, 0, sizeof(*arr) * (max + 1));

   for (int i = 0; i < n; ++i) {
       ++c[arr[i]]; // 1 2 1 3
       numOfReshuffle++;
   }

   int b = 0;
   for (int i = 0; i < max + 1; ++i) {
       for (int j = 0; j < c[i]; ++j) {
           arr[b++] = i;
           numOfReshuffle++;
       }
   }

   cout << "\n Массив отсортирован по возрастанию" << endl;
   cout << " Количество проверок условий: " << numOfCompare << endl;
   cout << " Количество перестановок элементов: " << numOfReshuffle << endl;
}

int main() {
   setlocale(LC_ALL, "RUSSIAN"); // Корректное отображение кириллицы в консоли

   int arr[SIZE]; // Массив
   int n; // Размер массива
   int choice; // Выбор необходимого действия
   cout << "Начальный размер массива(не должен превосходить " << SIZE << "): ";
   cin >> n; // Ввод размера массива

   // Обнуление массива
   for (int i = 0; i < n; ++i) arr[i] = 0;

   while (true) // Бесконечный цикл, где мы ждем выбор пользователя
   {
       cout << "\n Выбор действия:\n"
            << "1 - Заполнение массива псевдо случайными значениями \n"
            << "2 - Заполнение массива через пробел с консоли \n"
            << "3 - Вывод массива в консоль \n"
            << "4 - Сортировка массива по возрастанию методом подсчета \n"
            << "5 - Добавление одного элемента (размер массива после добавления не должен превосходить " << SIZE
            << ") \n"
            << "6 - Удаление элемента по индексу в массиве \n"
            << "7 - Количество различных чисел в массиве \n"
            << "8 - Завершение программы \n";
       cin >> choice; // Запрашиваем выбранный номер.
       switch (choice) {
           case 1:
               fillRandomArray(arr, n);// Заполнение массива псевдослучайными значениями от 0 до 10000
               break;
           case 2:
               putArray(arr, n);// Заполнение массива с консоли
               break;
           case 3:
               printArray(arr, n);// Вывод массива в консоль
               break;
           case 4:
               sort(arr, n); // Сортировка массива методом подсчета
               break;
           case 5:
               putSingleArrayElement(arr, n); // Вставка элемента в определенное место масива
               break;
           case 6:
               removeElement(arr, n); // Удалить элемент по индексу
               break;
           case 7:
               uniqueCount(arr, n); // Подсчитать количество уникальных элементов
               break;
           case 8:
               return 0;
           default: // Любой выбор, который мы не обрабатываем
               cout << "Введено неверное значение!" << endl;
               break;
       }
   }
}