9 класс. Раздел Программирование.
Тема урока. Сортировка массивов
Цели урока:
I. Формирование предметной компетенции:
Познавательные:
познакомить учащихся с основными алгоритмами сортировки одномерных массивов: сортировка методом выбора, сортировка методом обмена (метод "пузырька").
Практические:
отработка навыков ввода и редактирования программ на Паскале;
освоить и научить практически применять «пузырьковый» метод сортировки одномерного массива.
II. Формирование метапредметных компетенций:
Деятельностные компетенции (развивающие цели):
развивать логическое мышление, умение сопоставлять и делать выводы.
Социальные компетенции:
работать в команде, слушать и слышать учителя и одноклассников;
принимать решения, адекватно реагируя на ошибки.
План урока.
Постановка проблемы. Рассмотрение в игровой форме методов сортировки.
Реализация предложенных методов в виде программы.
Ввод и тестирование программы.
Итог урока.
Домашнее задание.
Сортировка – процесс размещения элементов заданного множества объектов в некотором определенном порядке, как правило, в порядке возрастания или убывания. (на доске) Записать определение в тетрадь.
Вопрос классу: Зачем нужна сортировка?
Легче работать с отсортированными данными, чем с произвольно расположенными данными:
поиск заданного элемента,
определение имеются ли пропущенные элементы,
сравнение двух массивов.
Можно использовать набор (8 – 10) палочек разной длины или другие однородные предметы: конфеты, камни и т.д. С закрытыми глазами упорядочить предметы на столе. (Индивидуальная работа)
Или Одному ученику завязываем глаза, перед доской выстраиваем 5-7 человек (игровые технологии). Задание: переставить учеников по росту – от самого низкого до самого высокого (проблема). Класс активно помогает. (Работа в группе)
Идет обсуждение и реализация предложений (мозговой штурм – проблемный метод).
Подводим итог обсуждения – формулируем методику сортировки.
Идея метода:
Для упорядочивания необходимо попарно сравнивать соседние элементы, если предшествующий элемент больше (меньше) последующего (пара не упорядочена), то элементы меняются местами (упорядочиваются). В результате одного прохода по массиву в конец массива выталкивается самый большой элемент – всплывает «пузырек». Поэтому при следующем проходе отсортированный элемент (отсортированные элементы) не просматривается (не просматриваются).
Такой метод получил название метод «пузырька»
Сортировка обменом (метод «пузырька»)
Введем понятие упорядоченной по возрастанию пары элементов A[i]<A[i+1] – пара упорядочена.
Формализуем задачу. Массив А заполнен 10-ю выбранными случайно двузначными числами. Отсортировать массив А по возрастанию значений.
Пример Значение | 25 | 36 | 12 | 19 | 58 | 98 | 32 | 45 | 36 | 77 | 1-й проход | 25 | 12 | 19 | 36 | 58 | 32 | 45 | 36 | 77 | 98 | 2-й проход | 12 | 19 | 25 | 36 | 32 | 45 | 36 | 58 | 77 |
| 3-й проход | 12 | 19 | 25 | 32 | 36 | 36 | 45 | 58 | ! |
| 4-й проход | 12 | 19 | 25 | 32 | 36 | 36 | 45 |
|
|
| 5-й проход | 12 | 19 | 25 | 32 | 36 | 36 |
|
|
|
| 6-й проход | 12 | 19 | 25 | 32 | 36 |
|
|
|
|
| 7-й проход | 12 | 19 | 25 | 32 |
|
|
|
|
|
| 8-й проход | 12 | 19 | 25 |
|
|
|
|
|
|
| 9-й проход | 12 | 19 |
|
|
|
|
|
|
|
|
Задания
Подсчитать количество произведенных сравнений.
Подсчитать количество произведенных перестановок.
Описать "пузырьковую" сортировку по убыванию.
Какие недостатки вы заметили?
Переходим к написанию программы Сортировка обменом
{1-заголовок программы}
program sort;
uses crt;
var a:array[1..10] of integer;
i,j,P:integer;
{2-заполнение массива случайными числами и вывод на экран в строку}
begin clrscr;randomize;
for i:=1 to 10 do
begin a[i]:=random(90)+10;
write(a[i],' ');
end;writeln;
{3-сортировка}
Если пара соседних элементов не упорядочена, то поменять элементы местами
if a[j]>a[j+1] then
begin P:=a[j];a[j]:=a[j+1];a[j+1]:=P;end;
Таких проверок-сравнений должно быть (сначала 9, потом -8, затем -7 и т.д. до?)
for j:=1 to 10-i do
if a[j]>a[j+1] then
begin P:=a[j];a[j]:=a[j+1];a[j+1]:=P;end;
Так как элементов в массиве 10, то для упорядочивания всего массива должно «всплыть» 9 (10-1) «пузырьков»
for i:=1 to 9 do
for j:=1 to 10-i do
if a[j]>a[j+1] then
begin P:=a[j];a[j]:=a[j+1];a[j+1]:=P;end;
{4-вывод отсортированного массива}
for i:=1 to 10 do
begin write(a[i],' ');end;
readln end.
Набрать программу и запустить на выполнение.
Устранить ошибки.
В нашем примере мы видели, что после 3-х проходов массив оказался отсортирован. Всегда ли так будет? Может ли оказаться, что потребуется 9 проходов?
Как избежать лишних проходов?
Признаком того, что массив отсортирован служит условие не(a[j]>a[j+1]) и, как следствие, серия команд begin P:=a[j];a[j]:=a[j+1];a[j+1]:=P;end не выполняется. Используем это. Возьмем логическую переменную flag:boolean, которая будет менять свое значение если серия P:=a[j];a[j]:=a[j+1];a[j+1]:=P выполнялась
flag:=false;
for j:=1 to 9 do
if a[j]>a[j+1] then
begin P:=a[j];a[j]:=a[j+1];a[j+1]:=P;flag:=true;end;
Теперь организуем цикл
repeat
until not flag;
Полный текст программы будет выглядеть так:
program sort;
uses crt;
var a:array[1..10] of integer;
j,P:integer;
flag:boolean;
{2-заполнение массива случайными числами}
begin clrscr;randomize;
for j:=1 to 10 do
begin a[j]:=random(90)+10;
write(a[j],' ');
end;writeln;
{3-сортировка}
repeat
flag:=false;
for j:=1 to 9 do
if a[j]>a[j+1] then
begin P:=a[j];a[j]:=a[j+1];a[j+1]:=P;flag:=true;end;
until not flag;
{4-вывод отсортированного массива}
for j:=1 to 10 do begin write(a[j],' ');end;
readln end.
Задание: изменить направление сортировки.
Идея второго метода: в неупорядоченной последовательности выбирается минимальный (максимальный) элемент и записывается на первое место. Этот элемент исключается из дальнейшей обработки. Оставшаяся последовательность элементов принимается за исходную. И процесс повторяется до тех пор, пока все элементы не будут выбраны.
Такой метод называют: сортировка выбором.
Значение | 5 | 15 | 7 | 9 | 1 | 8 | 16 | 4 | 10 | 2 | 1-й проход | 1 | 15 | 7 | 9 | 5 | 8 | 16 | 4 | 10 | 2 | 2-й проход |
| 2 | 7 | 9 | 5 | 8 | 16 | 4 | 10 | 15 | 3-й проход |
|
| 4 | 9 | 5 | 8 | 16 | 7 | 10 | 15 | 4-й проход |
|
|
| 5 | 9 | 8 | 16 | 7 | 10 | 15 | 5-й проход |
|
|
|
| 7 | 8 | 16 | 9 | 10 | 15 | 6-й проход |
|
|
|
|
| 8 | 16 | 9 | 10 | 15 | 7-й проход |
|
|
|
|
|
| 9 | 16 | 10 | 15 | 8-й проход |
|
|
|
|
|
|
| 10 | 16 | 15 | 9-й проход |
|
|
|
|
|
|
|
| 15 | 16 | Задание
Подсчитать количество произведенных сравнений.
Подсчитать количество произведенных перестановок.
Что можно сказать о лишних проходах?
Сравнить сортировку методами выбора и обмена по количеству сравнений и перестановок.
Какой метод эффективнее?
Программу сортировки методом выбора написать дома.
Итог урока:
Что такое сортировка?
Какова идея метода «пузырька»?
Какова идея метода выбора?
Какой метод эффективнее?
|
