Программирование на C++

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

Необходимые темы и конструкции C++:

• сортировка пузырьком, выбором и вставками
• быстрая сортировка и разбиение Хоара
• асимптотическая сложность O(...)
• устойчивость и сортировка на месте
• массивы, указатели и структуры

Структура проекта

Разместите решение в следующих файлах:

• main.cpp
• sorts.h
• sorts.cpp

Общие требования

• Соблюдайте указанные сигнатуры функций: ввод и вывод организуйте в main.
• Проверьте каждую функцию не менее чем на трёх наборах данных, включая граничный случай.
• Не используйте средства, которые не перечислены в разделе необходимых тем, если условие прямо их не разрешает.

Основные задания

1. Сортировка выбором с метриками

   Реализовать сортировку выбором по возрастанию. Дополнительно подсчитать число сравнений элементов и число обменов.

   Требуемая сигнатура:

   struct SortMetrics { long long comparisons; long long swaps; };
   SortMetrics selection_sort(int* data, int size);

   Требования:

   • Считайте только сравнения элементов массива, а не проверки границ циклов.
   • Объясните, почему число сравнений не зависит от начального порядка.

   Входные данные / вызов	Результат
   [4, 1, 3, 2]	[1, 2, 3, 4]; comparisons=6

2. Устойчивая сортировка измерений

   Записи содержат значение измерения и его исходный номер. Упорядочить записи по значению устойчивой сортировкой вставками.

   Требуемая сигнатура:

   struct Measurement { int value; int original_index; };
   void insertion_sort(Measurement* data, int size);

   Требования:

   • При равных значениях исходные номера должны остаться в прежнем взаимном порядке.

   Входные данные / вызов	Результат
   (3,0), (1,1), (3,2), (2,3)	(1,1), (2,3), (3,0), (3,2)

3. Быстрая сортировка

   Реализовать разбиение по схеме Хоара и рекурсивную быструю сортировку массива. Проверьте уже упорядоченный, обратно упорядоченный массивы и массив одинаковых элементов.

   Требуемая сигнатура:

   int partition(int* data, int left, int right);
   void quick_sort(int* data, int left, int right);

   Требования:

   • Опорный элемент выберите из середины обрабатываемого диапазона.
   • Для каждого рекурсивного вызова диапазон должен строго уменьшаться.

4. Быстрая сортировка

   Решить предыдущую задачи при помощи стандартной функции qsort

Домашнее задание

1. Упорядочение строк матрицы

   Упорядочить строки квадратной матрицы по возрастанию их первых элементов. Переставлять нужно строки целиком.

   Требуемая сигнатура:

   constexpr int SIZE = 5;
   void sort_rows(int matrix[][SIZE]);

   Требования:

   • Используйте один из трёх простых методов сортировки.
   • Дополнительную матрицу не создавайте.

2. Индексная сортировка

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

   Требуемая сигнатура:

   void index_sort(const double* values, int size, int* indices);

   Требования:

   • При равных значениях меньший исходный индекс должен идти раньше.

   Входные данные / вызов	Результат
   [4.5, 1.0, 4.5, -2.0]	[3, 1, 0, 2]

3. Влияние исходного порядка

   Для сортировки пузырьком с досрочным завершением подсчитать сравнения и обмены на случайном, уже отсортированном и обратно отсортированном массивах одинакового размера.

   Требуемая сигнатура:

   SortMetrics bubble_sort(int* data, int size);

   Требования:

   • Случайный массив создайте средствами <random> с фиксированным seed.
   • По результатам сформулируйте вывод о лучшем и худшем случаях.