Проход 1. Начинаем со второй позиции. 9
 Скачать 1.43 Mb.
|
 СОДЕРЖАНИЕ Введение 3 3. Сортировка вставками 9 В сортировке вставками начинаем со второго элемента. Проверяем между собой второй элемент с первым и, если надо, меняем местами. Сравниваем следующую пару элементов и проверяем все пары до нее. 9 Проход №1. Начинаем со второй позиции. 9 9 Рисунок 10. 9 Число 12 больше 5 — элементы меняются местами. 9 Проход №2. Начинаем с третьей позиции. 9 Проверяем вторую и третью позиции. Затем первую и вторую. 9 9 Рисунок 11. 9 Проход №3. Начинаем с четвертой позиции. 10 10 Рисунок 12. 10 Произошло три смены местами. 10 Проход №4. Начинаем с последней позиции 11 11 Рисунок 12. 11 Получаем отсортированный массив на выходе. 12 ЗАКЛЮЧЕНИЕ 13 Список использованных источников 13 4.HappyCoders - Уроки программирования, алгоритмы, статьи, исходники, примеры программ и полезные советы: [Электронный ресурс]. URL: https://www.happycoders.eu/algorithms/sorting-algorithms/ 13 14 Введение Алгоритм сортировки - это алгоритм, который упорядочивает элементы списка. Наиболее часто используемыми порядками являются числовой порядок и лексикографический порядок, а также возрастание или убывание. Эффективная сортировка важна для оптимизации эффективности других алгоритмов (таких как алгоритмы поиска и объединения), которые требуют, чтобы входные данные находились в отсортированных списках. Сортировка также часто полезна для канонизации данных и для получения удобочитаемых выходных данных. Формально выходные данные любого алгоритма сортировки должны удовлетворять двум условиям: Вывод осуществляется в монотонном порядке (каждый элемент не меньше / не больше предыдущего элемента, в соответствии с требуемым порядком). Результат представляет собой перестановку (изменение порядка, но с сохранением всех исходных элементов) входных данных. Для оптимальной эффективности входные данные должны храниться в структуре данных, которая допускает произвольный доступ, а не тот, который допускает только последовательный доступ. Целью работы является ознакомиться и реализовать простые методы сортировки — Пузырьковая сортировка; Сортировка выбором; Сортировка вставками. 1. Пузырьковая сортировка В пузырьковой сортировке каждый элемент сравнивается со следующим. Если два таких элемента не стоят в нужном порядке, то они меняются между собой местами. В конце каждой итерации (далее называем их проходами) наибольший/наименьший элемент ставится в конец списка. Прежде чем писать код, разберем сортировку визуально на примере массива из пяти элементов. Отсортируем его в порядке возрастания.  Рисунок 1. Проход №1 Оранжевым отмечаются элементы, которые нужно поменять местами. Зеленые уже стоят в нужном порядке.  Рисунок 2. Наибольший элемент — число 48 — оказался в конце списка. Проход №2  Рисунок 3. Наибольший элемент уже занимает место в конце массива. Чтобы поставить следующее число по убыванию, можно пройтись лишь до 4-й позиции, а не пятой. Проход №3  Рисунок 4. Проход №4  Рисунок 5. После четвертого прохода получаем отсортированный массив. Функция сортировки в качестве параметров будет принимать указатель на массив и его размер. Функцией swap() элементы меняются местами друг с другом:  Код пузырьковой сортировки  Результат сотртировки 2. Сортировка выбором Ищем наименьшее значение в массиве и ставим его на позицию, откуда начали проход. Потом двигаемся на следующую позицию. Возьмем тот же массив из пяти элементов и отсортируем его. Проход №1  Рисунок 6. Зеленым отмечается наименьший элемент в подмассиве — он ставится в начало списка. Проход №2 Число 4 — наименьшее в оставшейся части массива. Перемещаем четверку на вторую позицию после числа 0.  Рисунок 7. Проход №3  Рисунок 8. Проход №4  Рисунок 9. Напишем функцию поиска наименьшего элемента и используем ее в сортировке:  Код сортировки выбора  Результат сортировки 3. Сортировка вставками В сортировке вставками начинаем со второго элемента. Проверяем между собой второй элемент с первым и, если надо, меняем местами. Сравниваем следующую пару элементов и проверяем все пары до нее. Проход №1. Начинаем со второй позиции.  Рисунок 10. Число 12 больше 5 — элементы меняются местами. Проход №2. Начинаем с третьей позиции. Проверяем вторую и третью позиции. Затем первую и вторую.  Рисунок 11. Проход №3. Начинаем с четвертой позиции.  Рисунок 12. Произошло три смены местами. Проход №4. Начинаем с последней позиции  Рисунок 12. Получаем отсортированный массив на выходе.  Код сортировки вставками  Результат сортировки ЗАКЛЮЧЕНИЕ Список использованных источников Software Testing Help: [Электронный ресурс]. URL: https://www.softwaretestinghelp.com/sorting-techniques-in-cpp/ Medium – Полезные советы и примеры программ: [Электронный ресурс]. URL: https://medium.com/@ssbothwell/sorting-algorithms-and-big-o-analysis-332ce7b8e3a1 Programiz – Туториал по написаннию программ на разных языках программирования: [Электронный ресурс]. URL: https://www.programiz.com/dsa/shell-sort HappyCoders - Уроки программирования, алгоритмы, статьи, исходники, примеры программ и полезные советы: [Электронный ресурс]. URL: https://www.happycoders.eu/algorithms/sorting-algorithms/ |