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



Урок 26
Сортировка массивов
§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качать материалы урока







Наверх