Методические указания к практическому занятию № 34
Тема: «Сортировка и поиск»
Количество часов: 2.
Цели:
- обучающая: освоить основные алгоритмы сортировки, написать программу с использованием этих алгоритмов; научить анализировать, выделять главное, существенное при решении задачи, самостоятельно работать;
- воспитательная: выработать умение мыслить, научить логически мыслить; оценить степень работоспособности; развивать познавательные возможности, внимание; содействовать развитию профессиональных качеств;
- развивающая: развивать умения и навыки применять: теорию при решении задач, навыки самостоятельной работы с методическими указаниями к практическому занятию, осуществлять самоконтроль, язык терминов.
Задания:
1. Общие понятия.
2.Алгоритмы сортировки: метод пузырька.
3. Алгоритмы сортировки: сортировка выбором.
4. Алгоритмы сортировки: быстрая сортировка.
5. Поиск элемента.
Выводы: выполнение практической работы способствует формированию практических навыков по созданию прикладных приложений сортировки и поиска данных.
МЕТОДИЧЕСКИЕ УКАЗАНИЯ К ВЫПОЛНЕНИЮ:
- Общие понятия
Сортировка - это процесс упорядочения элементов массива или списка по возрастанию или убыванию.
Существует много алгоритмов сортировки, отличающихся по ряду характеристик:
1) время работы, или вычислительная сложность, - количество операций, затрачиваемых алгоритмом. Обычно оценивается худший сценарий, когда исходный массив оказывается максимально непорядочен с точки зрения алгоритма;
2) затрачиваемая память ( помимо исходного массива ) - некоторые ал горитмы требуют выделения дополнительной памяти для временного хранения данных или формирования нового выходного массива.
Кроме того, алгоритмы можно разделить по типу доступа к данным:
- алгоритмы внутренней сортировки применяются для сортировки данных, целиком находящихся в оперативной памяти;
- алгоритмы внешней сортировки оперируют данными, не поме щающимися в оперативную память. Такие алгоритмы используют внешнюю память, доступ к которой требует существенно большего времени, поэтому требуются специальные алгоритмические решения, чтобы каждый элемент использовался алгоритмом минимальное количество раз.
- Алгоритмы сортировки: метод пузырька
Метод пузырька является достаточно простым и поэтому получил широкое распространение. Вычислительная сложность алгоритма квадратичная - O(n2), поэтому алгоритм эффективен только на небольших массивах данных.
Алгоритм проходит все элементы массива и попарно сравнивает их друг с другом. Если порядок сравниваемых элементов неверный, алгоритм меняет элементы местами.
- Алгоритмы сортировки: сортировка выбором
Сортировка выбором имеет квадратичную сложность O(n2) и, как и предыдущий метод пузырька, эффективен лишь на небольших объемах данных.
Алгоритм находит номер минимального значения в текущем списке, меняет этот элемент со значением первой неотсортированной позиции (если минимальный элемент не находится на данной позиции), а затем сортирует хвост списка, исключив из рассмотрения уже отсортированные элементы.
- Алгоритмы сортировки: быстрая сортировка
Алгоритм быстрой сортировки является одним из самых быстрых алгоритмов сортировки: в лучшем случае он имеет логарифмическую сложность, в худшем - квадратичную. Алгоритм выполняется следующим образом:
1. Выбирается некоторый элемент, который называется опорным.
2. Реорганизуем массив таким образом, чтобы все элементы, меньшие или равные опорному элементу, оказались слева от него, а все элементы, больше опорного, - справа от него.
3. Рекурсивно упорядочиваем массивы, лежащие слева и справа от опорного элемента.
Поиск элемента
Алгоритмы поиска позволяют найти индекс элемента с требуемым значением.
1) Если массив не упорядочен, то возможен лишь простой поиск: перебор всех элементов массива до тех пор, пока не встретится элемент с нужным значением или не закончится массив. Если элемент найден, поиск должен быть прекращен, поскольку дальнейший просмотр массива не имеет смысла.
Если алгоритм поиска не нашел подходящий элемент, он должен каким-то образом сигнализировать об этом вызывающей программе. Чаще всего в таком случае возвращается значение -1 - число, которое заведомо не может использоваться в качестве индекса массива.
Вычислительная сложность алгоритма простого поиска - линейная O(n).
2) Если массив упорядочен по возрастанию, то возможно использование дихотомического рекурсивного алгоритма: массив каждый раз делится пополам, и если искомый элемент меньше среднего, то поиск продолжается в левой его половине, иначе - в правой.
Вычислительная сложность алгоритма - логарифмическая.
Индивидуальное задание 1.
Общая часть задания: сформировать массив из 100 случайных чисел. Выполнить простой поиск элемента, подсчитать количество итераций. Отсортировать массив всеми рассмотренными методами и посчитать количество итерация для каждого метода. Выполнить поиск элемента методом дихотомии, подсчитать количество итераций. Сделать выводы.
Вопросы для самоконтроля:
1. Сортировка: общие понятия.
2.Алгоритмы сортировки: метод пузырька.
3. Алгоритмы сортировки: сортировка выбором.
4. Алгоритмы сортировки: быстрая сортировка.
5. Поиск элемента.
Список литературы и ссылки на Интернет-ресурсы, содержащие информацию по теме:
Основная литература:
1. Дёмин, А.Ю. Лабораторный практикум по информатике [Электронный ресурс]: учебное пособие / А.Ю. Дёмин, В.А. Дорофеев; Томский политехнический университет. – Томск: Изд-во Томского политехнического университета, 2014. – 132 с. — Режим доступа: https://portal.tpu.ru/SHARED/a/AD/Education/Tab1/workbook_Informatic.pdf.
2. Мейер, Б. Объектно-ориентированное программирование и программная инженерия [Электронный ресурс]/ Мейер Б.— Электрон. текстовые данные. — М.: Интернет-Университет Информационных Технологий (ИНТУИТ), 2016. — 285 c. — Режим доступа: http://www.iprbookshop.ru/39552.