Список учебной и дополнительной литературы

Сортировка выбором

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

Алгоритм сортировки прямым выбором по убыванию

Рассмотрим алгоритм сортировки выбором. Суть ее в случае упорядочивания по убыванию заключается в следующем. Будем просматривать массив слева направо. Найдем максимальный элемент в массиве и поменяем его с первым элементом. Затем найдем максимальный элемент среди оставшихся элементов и поменяем его со вторым элементом. На N-1 шаге мы закончим упорядочивание нашего массива, состоящего из N элементов [2].

Алгоритм сортировки прямым выбором по возрастанию

Далее сформулируем особенности программирования сортировки выбором. Структура алгоритма должна представлять собой два вложенных цикла. Внешний цикл – проходы по массиву, внутренний цикл – поиск необходимого элемента и обмен элементов массива.

Сортировка обменом или «пузырьковая» сортировка

«Пузырьковая» сортировка традиционно считается более простой в реализации [2].

Алгоритм сортировки обменом или «пузырьковая» сортировка по возрастанию

Суть упорядочивания по возрастанию заключается в следующем. Просматриваем слева направо все пары соседних элементов. Если при этом рассматриваемый элемент массива больше следующего, то элементы меняем местами. В результате такого просмотра массива максимальный элемент окажется на крайнем справа (своём) месте. Будем просматривать массив снова, исключив из рассмотрения правый элемент. На своем месте теперь окажется уже второй по величине элемент. В последнем просмотре будут участвовать только первый и второй элементы. Общее число просмотров массива из N элементов при этом равно N-1 [2].

Пузырьковая» сортировка по убыванию

Далее формулируем особенности программирования сортировки обменом. Структура алгоритма должна представлять собой два вложенных цикла. Внешний цикл – проходы по массиву, внутренний цикл – сравнение пар элементов и обмен, если это необходимо.

Усовершенствованная «пузырьковая» сортировка

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

Практическая работа

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

1. Выполнить сортировку только четных элементов массива (нечетные элементы остаются на своих местах)

Примерный вариант решения задачи:

2. Выполнить сортировку элементов, записанных на нечетных местах [4].

Примерный вариант решения задачи:

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

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

Список учебной и дополнительной литературы

1. Семакин И.Г. Информатика и ИКТ: учебник для 9 класса. Москва, БИНОМ. Лаборатория знаний, 2010.
2. Андреева Е.В. Программирование – это так просто, программирование – это так сложно. Современный учебник программирования. – М.: МЦНМО, 2009.
3. Златопольский Д.М. Программирование: типовые задачи, алгоритмы, методы. Москва, БИНОМ. Лаборатория знаний,2007.
4. Окулов С.М. Основы программирования. Москва, БИНОМ. Лаборатория знаний, 2010.