Индивидуальное задание 1

Методические указания к практическому занятию № 34

Тема: «Сортировка и поиск»

Количество часов: 2.

Цели:

- обучающая: освоить основные алгоритмы сортировки, написать программу с использованием этих алгоритмов; научить анализировать, выделять главное, существенное при решении задачи, самостоятельно работать;

- воспитательная: выработать умение мыслить, научить логически мыслить; оценить степень работоспособности; развивать познавательные возможности, внимание; содействовать развитию профессиональных качеств;

- развивающая: развивать умения и навыки применять: теорию при решении задач, навыки самостоятельной работы с методическими указаниями к практическому занятию, осуществлять самоконтроль, язык терминов.

Задания:

1. Общие понятия.

2.Алгоритмы сортировки: метод пузырька.

3. Алгоритмы сортировки: сортировка выбором.

4. Алгоритмы сортировки: быстрая сортировка.

5. Поиск элемента.

Выводы: выполнение практической работы способствует формированию практических навыков по созданию прикладных приложений сортировки и поиска данных.

 

МЕТОДИЧЕСКИЕ УКАЗАНИЯ К ВЫПОЛНЕНИЮ:

1. Общие понятия

Сортировка - это процесс упорядочения элементов массива или списка по возрастанию или убыванию.

Существует много алгоритмов сортировки, отличающихся по ряду характеристик:

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

2) затрачиваемая память ( помимо исходного массива ) - некоторые ал ­ горитмы требуют выделения дополнительной памяти для временного хранения данных или формирования нового выходного массива.

Кроме того, алгоритмы можно разделить по типу доступа к данным:

- алгоритмы внутренней сортировки применяются для сортировки данных, целиком находящихся в оперативной памяти;

- алгоритмы внешней сортировки оперируют данными, не поме ­ щающимися в оперативную память. Такие алгоритмы используют внешнюю память, доступ к которой требует существенно большего времени, поэтому требуются специальные алгоритмические решения, чтобы каждый элемент использовался алгоритмом минимальное количество раз.

 

1. Алгоритмы сортировки: метод пузырька

Метод пузырька является достаточно простым и поэтому получил широкое распространение. Вычислительная сложность алгоритма квадратичная - O(n²), поэтому алгоритм эффективен только на небольших массивах данных.

Алгоритм проходит все элементы массива и попарно сравнивает их друг с другом. Если порядок сравниваемых элементов неверный, алгоритм меняет элементы местами.

 

1. Алгоритмы сортировки: сортировка выбором

Сортировка выбором имеет квадратичную сложность O(n²) и, как и предыдущий метод пузырька, эффективен лишь на небольших объемах данных.

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

 

1. Алгоритмы сортировки: быстрая сортировка

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

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.