Конспект урока "Сортировка одномерных массивов" 10 класс

Кокин Дмитрий Николаевич, учитель информатики и ИКТ, школа 707
Дата: 5.12.08
Класс: 10 «1»
Номер урока: 4
Тема урока: Сортировка одномерных массивов
Дидактическая цель:
расширить знания о массивах в языке Паскаль
углубить знания о массивах в языке Паскаль
углубить навыки программирования на языке Паскаль
разъяснить сущность сортировки массива
разъяснить применение сортировки
Задачи обучения:
Знать определение сортировки
Понимать назначение сортировки
Понимать процесс сортировки
Задачи развития:
познавательных интересов
навыков работы на компьютере
системно-комбинаторного мышления
логико-алгоритмического мышления
Воспитательные задачи:
воспитание информационной культуры учащихся
внимательности
аккуратности
дисциплинированности
усидчивости
Тип урока: комбинированный.
Основная форма организации обучения на уроке: фронтальная.
Средства обучения: доска, компьютер, компьютерная презентация
Список литературы:
1. Угринович «Информатика и ИКТ. Базовый курс. Учебник 10-11 класса.»
2. Информатика. Базовый курс. 10 класс И. Семакин, Л. Залогова, С. Русаков, Л. Шестакова, Москва
2005 БИНОМ Лаборатория знаний
Метод обучения: иллюстративный.
План урока:
1. Орг. момент. (2 мин)
2. Подготовка учащихся к активному освоению материала. (4 мин)
3. Проверка Д\З (6 мин)
4. Теоретическая часть. (30 мин)
5. Итог урока. (3 мин)
Ход урока:
Этапы урока
Деятельность учителя
Деятельность учащихся
Организационный
момент.
2 минута
Приветствие.
Подготовка
учащихся к
активному
освоению
материала.
2 минут
Следующей темой в нашем блоке посвященном
программированию будет тема под названием
«Сортировка одномерных массивов». Запишите ее в
тетрадь.
Сортировка одномерных
массивов
Введение нового
материала
Давайте подумаем что такое сортировка?
В тетрадь.
Сортировкой называется распределение элементов
множества в соответствии с определенными правилами.
Мы с вами будем говорить о сортировки чисел.
Пример сортировки чисел.
5 2 3 7 1 => 7 5 3 2 1
Как называется такая сортировка?
Как будет выглядеть этот же массив отсортированный по
возрастанию?
А зачем вообще нужна сортировка?
Вы когда-нибудь задумывались почему например слова в
словаре расположены по алфавиту?
Правильно сортировка главным образом нужна для того
чтобы ускорить поиск. А давайте подумаем чтобы было
если бы слова были расположены в случайном порядке
как бы сильно увеличилось время поиска нужного слова.
На практике можно утверждать что гораздо быстрее
Расположение чего либо
по возрастанию или в
каком либо порядке.
Сортировкой называется
распределение элементов
множества в соответствии
с определенными
правилами.
По убыванию
1 2 3 5 7
Чтобы быстрее искать
отсортировать массив и найти в нем элемент, чем искать
элемент в не отсортированном массиве.
Алгоритмов сортировки достаточно много. Во всех есть
некая закономерность, чем эффективнее алгоритм тем он
более сложен. Ну и наоборот соответственно. Мы с вами
рассмотрим один из самых простых и называется он
метод «Пузырька».
Почему он назван так. Вот вы когда-нибудь кипятили
воду? Заметили что самые большие пузыри воздуха
поднимаются самыми первыми?
Вот отсюда и появилось название алгоритма. Т.к. в этом
алгоритме самым первым отсортированным элементом
будет самое большое число. Оно первое займет свою
позицию в массиве. И так по убывающей.
Давайте посмотрим как работает алгоритм.
Есть произвольный массив элементов. Например
шариков. Задача отсортировать массив по убыванию.
Начиная с первого элемента сравниваем его с
отсальными. То есть. 1 и 2, 1 и3, 1 и 4.
Если элемент который левее меньше то меняем их
местами.
Смотрим шарики. 1 и 2 – левый меньше правого? –Нет.
Значит идем дальше 1 и 3 – левый меньше правого? – Да.
Меняем их местами. Получаем.
Сравниваем 1 и 4. Левый меньше правого? –Нет.
Видите самый большой элемент встал на 1 позицию. Как
бы всплыл самый большой пузырек. Повторяем со 2
элементом.
Но поскольку мы теперь знаем что 1 элемент уже
отсортирован то далее в сортировке он не участвует.
Сравниваем 2 и 3 элемент. Левый меньше правого? – Да .
Переставляем
Сравниваем 2 и 4 элемент. Левый меньше правого? – Нет
.
Теперь уже 2 элемента заняли свои позиции.
Теперь 3 элемент. Здесь всего 1 сравнение 3 и 4. Левый
меньше правого? – Да. Переставляем
Все алгоритм окончен и мы получили отсортированный
по убыванию массив.
Давайте нарисуем блок схему. Алгоритма.
Как видите телом одного цикла является другой цикл.
Начало
a(n)
i = 1, n -1
j = i + 1, n
t = a[i]
a[i] = a[j]
a[j] = t
a(n)
Конец
ДА
НЕТ
Раньше вы с таким не встречались. В этом нет ничего
страшного вполне обычный ход.
Так же хочу обратить внимание на первый цикл – как вы
думает почему до n-1 а не до n?
Потому что в конце остается 1 элемент и он само собой
на своем месте.
Итак давайте решим задачу.
Запишем ее в тетрадь.
Создать массив целых чисел при помощи генератора
случайных чисел в диапазоне [0;9], размерностью 5.
Вывести его на экран, отсортировать и снова вывести на
экран.
Рассмотрим решение.(запишите в тетрадь)
uses crt;
var
a:array [1..5] of integer;
i,j,t:integer;
begin
clrscr;
randomize;
for i:=1 to 5 do
a[i]:=random(10);
for i:=1 to 5 do
write(a[i]:2);
writeln;
for i:=1 to 4 do
for j:=i+1 to 5 do
if a[i]<a[j] then begin
t:=a[i];
a[i]:=a[j];
a[j]:=t;
end;
for i:=1 to 5 do
write(a[i]:2);
readln;
end.
Все вам здесь знакомо – рассмотрим саму сортировку
for i:=1 to 4 do
for j:=i+1 to 5 do
if a[i]<a[j] then begin
t:=a[i];
a[i]:=a[j];
a[j]:=t;
end;
Вот как и на блок схеме 2 цикла один является телом
другого. Сравнивается каждый элемент с оставшимися
если левый меньше то перестановка. Всем понятен
алгоритм?
Тогда перейдем к практики.
Практическая часть.
Ваша задача. Подобна той что мы разбирали. С
некоторыми изменениями.
Создать массив целых чисел при помощи генератора
случайных чисел в диапазоне [0;20], размерностью 10.
Вывести его на экран, отсортировать и снова вывести на
экран. Так чтобы каждый элемент одного был выведен
под соответствующим элементом другого массива.
Пересаживайтесь за компьютеры.
Доп задания
1. сортировка по возрастанию
2. Диапазон от [-20; 20] (поползет вывод)
Критерий оценки.
Переписано из тетради – 3
Решена практическая задача – 4
Доп задание - 5
Домашнее задание
Написать программу в тетради.
Дан массив баллов полученных участницами конкурса
красоты. Вывести на экран баллы участниц занявших
первые 3 места.
Подведение итогов
Оглашение оценок
Сегодня вы научились сортировать одномерные массивы
целых чисел, что дополнило багаж ваших знаний по теме
программирования. Сортировка очень мощный и
необходимый инструмент используемый очень часто в
различных задачах.
Спасибо за урок все свободны.