4 - сортировка одномерного числового массива

Лабораторная работа 4 для студентов курса “Основы программирования” 1 курса кафедры ИУ5 МГТУ им Н.Э. Баумана.

Содержание

• Цель работы
• Начало работы
• Указания по выполнению лабораторной работы
  • Общие советы
  • Сортировка выбором (selection sort, min/max)
  • Сортировка пузырьком (bubble sort)
  • Генератор псевдо-случайных чисел
• Задание

Цель работы

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

Начало работы

Зайдите в свою локальную директорию с репозиторием для выполнения лабораторных работ. Заберите ветку с соответствующей лабораторной работой из общего репозитория (в лабораторной работе 0 был отмечен меткой upstream):

git pull upstream

или

git pull upstream lab_4

Переключитесь на ветку с текущей лабораторной работой:

git checkout lab_4

Свяжите ветку локального репозитория с вашим удаленным репозиторием:

git push --set-upstream origin lab_4

Указания по выполнению лабораторной работы

Для данной лабораторной работы действуют все требования, указанные в третьей лабораторной работе.

Общие советы

• Размер статического массива может задаваться только такой константой или выражением, которые могут быть посчитаны на стадии компиляции;
• Автоматического контроля выхода за пределы границы массива не производится, следовательно за этим надо следить самостоятельно;
• В указателе хранится адрес какой-то ячейки памяти (которая может быть адресом начальной ячейки области памяти);
• Массивы неявно приводятся к указателю соответствующего типа. Имя массива является указателем на его нулевой элемент:

int arr[] = {1, 2};
// arr - адрес arr[0], arr == &arr[0], *arr == arr[0]

• Память на куче динамически выделяется и освобождается с помощью операторов new и delete соответственно для одной переменной. Для выделения/освобождения области памяти используются операторы new[] и delete[].
• Количество вызовов new (new[]) должно соответствовать количеству вызовов delete (delete[]);
• Если не освободить память, на которую указывает некоторый указатель внутри функции (локальная переменная), то произойдет утечка памяти:

void Example() {
    int* p = new int{};
}
// значение p (адрес памяти, выделенной на куче через оператор new) утеряно, память освободить невозможно -> утечка памяти

• Область памяти, выделяемая на куче (как и на стеке, но не в статической памяти), не инициализируется какими-либо значениями автоматически. Если есть гарантия, что все элементы массива будут проинициализированы до чтения, то его можно не инициализировать при объявлении (как на стеке, так и на куче). Чтение из неинициализированной памяти ведет к UB;
• Для индексации по массиву и для хранения его размера (а также в целом для разных счетчиков, id и т.п.) используйте тип size_t.
• Указатель может иметь значение nullptr. Это значит, что он не хранит адрес валидной ячейки памяти, следовательно такой указатель нельзя разыменовывать. Всегда проверяйте указатель на nullptr, при получении его в качестве параметра внутри функции.

Сортировка выбором (selection sort, min/max)

Алгоритм сортировки, имеющий худшее, среднее и лучшее время выполнения O(n²). Затраты памяти O(1).

Работает следующим образом:

1. Находится минимальный (или максимальный) элемент в массиве;
2. Найденное значение обменивается со значением первого (если ищется минимальный элемент) или последнего (если ищется максимальный элемент) неотсортированного элемента;
3. Сортируется оставшаяся часть массива (отсортированные элементы не рассматриваются).

Сортировка пузырьком (bubble sort)

Алгоритм сортировки, имеющий худшее и среднее время выполнения O(n²). Лучшее время выполнения O(n). Затраты памяти O(1).

Работает следующим образом:

1. В цикле попарно сравниваются элементы массива;
2. Если первый элемент больше второго, то их значения обмениваются между собой;
3. Цикл повторяется либо n - 1 раз, либо пока не обнаружится, что перестановки элементов больше не требуются.

Генератор псевдо-случайных чисел

В стандартной библиотеке C++ представлен заголовочный файл random, в котором содержатся инструменты для генерации псевдо-случайных чисел.

В самом простом случае для генерации случайных чисел в C++ достаточно 3 вещи:

• Random engine - класс, который содержит алгоритм генерации псевдо-рандомных чисел;
• Сид (англ. seed, зерно) - некоторое значение, которое инициализирует конкретный объект random engine. При одинаковых значениях сида последовательность генерируемых чисел будет одинакова. Например, если при запуске генератор выдал последовательность вида [1, 5, 0, 12], то при повторном запуске (то есть если создать новый генератор, но с таким же алгоритмом и сидом), то он также выдаст последовательность [1, 5, 0, 12];
  • Способ выбора значения сида зависит от того, как именно планируется использовать генератор случайных чисел. В случае данной лабораторной работы, где нет каких-то специфичных требований к генерируемым числам, кроме того, чтобы они казались случайными, в качестве источника сида можно использовать std::random_device, который может работать, например, на основе показателей аппаратного обеспечения и прочих источников “рандомных” данных (таких как текущая температура процессора, потребляемая мощность, изменения координат курсора мыши, и т.д.);
• Распределение - в каком диапазоне и как именно будут распределяться генерируемые числа (равномерное, нормальное распределения и т.п.).

Пример:

std::random_device r{}; // инициализация std::random_device
std::default_random_engine randomEngine(r()); // создание random engine с сидом, сгенерированным r
std::uniform_int_distribution distribution(1, 12); // равномерное распределение от 1 до 12
for (int i = 0; i < 100; ++i) {
    std::cout << distribution(randomEngine) << std::endl;
} // выведет 100 равномерно распределенных псевдо-случайных чисел от 1 до 12

Задание

Реализовать следующие методы сортировки массивов:

• Сортировка выбором;
• Сортировка пузырьком.

Заполнить массив рандомными элементами (целые числа, равномерное распределение от 0 до 99).

Для статических массивов небольшого размера (5-10 элементов):

• Вывести исходный массив;
• Трижды отсортировать массив двумя методами (элементы массива, подаваемых функциям сортировки, должны быть одинаковы). После каждой сортировки вывести значения отсортированного массива, количество перестановок и сравнений (для каждого метода):
  • Отсортировать исходный (неотсортированный) массив по возрастанию;
  • Отсортировать получившийся массив по возрастанию (заново);
  • Отсортировать получившийся массив по убыванию.

Для динамических массивов:

• Дать возможность задать размер массива;
• Отсортировать массив двумя методами (элементы массива, подаваемых функциям сортировки, должны быть одинаковы). Для каждого метода вывести количество перестановок и сравнений.

Вывод должен быть оформлен в виде отформатированной таблицы.

Проанализировать быстродействие алгоритмов сортировки (на основе количества перестановок и сравнений).