Планирование уроков на учебный год (по учебнику К.Ю. Полякова, Е.А. Еремина, полный углубленный курс, 4 часа в неделю)



Уроки 92 - 94
Сортировка массивов
§64. Сортировка




Содержание урока

Введение

Метод пузырька (сортировка обменами)

Метод выбора

«Быстрая сортировка»

Вопросы и задания

Задачи


Метод пузырька (сортировка обменами)


Название этого метода произошло от известного физического явления — пузырёк воздуха в воде поднимается вверх. Если говорить о сортировке массива, сначала поднимается «наверх» (к началу массива) самый «лёгкий» элемент (элемент с минимальными значениями), затем следующий и т. д.

Сначала сравниваем последний элемент с предпоследним. Если они стоят неправильно (меньший элемент «ниже»), то меняем их местами. Далее так же рассматриваем следующую пару элементов и т. д. (рис. 8.11).

Рис. 8.11

Рис. 8.11

После обработки пары (А[1], А[2]) минимальный элемент стоит на месте А[1]. Это значит, что на следующих этапах его можно не рассматривать. Первый цикл, устанавливающий на свое место первый (минимальный) элемент, можно на псевдокоде записать так:

Здесь j — целочисленная переменная. Обратите внимание, что на очередном шаге сравниваются элементы А[j] и А[j+1], поэтому цикл начинается с j = N - 1. Если начать с j = N, то на первом же шаге получаем выход за границы массива — обращение к элементу А[N+1].

За один проход такой цикл ставит на место один элемент. Чтобы «подтянуть» второй элемент, нужно написать ещё один почти такой же цикл, который будет отличаться только конечным значением j в заголовке цикла. Так как верхний элемент уже стоит на месте, его не нужно трогать:

При установке 3-го элемента конечное значение для j будет 3 и т. д. Таких циклов нужно сделать N - 1: на 1 меньше, чем количество элементов массива. Почему не N? Дело в том, что если N - 1 элементов поставлены на свои места, то оставшийся автоматически встает на своё место — другого места нет. Поэтому полный алгоритм сортировки представляет собой такой вложенный цикл:

Записать полную программу на выбранном языке вы можете самостоятельно.

Следующая страница Метод выбора



Cкачать материалы урока







Наверх