Разработка урока "Методы сортировки числовых массивов"
план-конспект урока по информатике и икт (10 класс)

Марданова Гульсина Насиховна,

учитель информатики

первой квалификационной категории

МБОУ №СОШ № 9 НМР РТ

Урок информатики в 10 классе химико-биологического профиля.

Тема «Методы сортировки массива»

Тип урока: комбинированный

Цели урока:

Образовательная:

повторить основные понятия по теме «Обработка массивов»; познакомить с методами сортировки  массива; реализовать алгоритм на языке программирования.

 Развивающая:

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

Воспитательная:

воспитывать информационную культуру учащихся, самостоятельность, внимательность.

Задачи урока:

1. Рассмотреть подробно «пузырьковый» метод сортировки массива.

2. Познакомиться с другими методами сортировки массива.

3. Составить программу для сортировки числового массива.

Оборудование: ПК, интерактивная доска, мультимедиапроектор, программное обеспечение

Основные понятия: массив, алгоритмы ввода и вывода массива, методы сортировки массива, трассировочная таблица.

План урока

1. Организационный момент
2. Актуализация знаний
3. Сообщение темы и постановка целей урока.
4. Объяснение нового материала
5. Закрепление изученного материала
6. Подведение итогов урока

Этапы урока.

1. Приветствие. Проверка готовности к уроку.

2. Актуализация.  Работа по карточкам, с доской.

1. Сколько раз отработает цикл? Чему будет равно значение переменной a?

k:=4; a:=2;

repeat

a:=a+1;

k:=k-1;

until k=0;  (4 раза, а=6)

a:=0;

for  i:=1 to 3 do

  for  j:=1 to 2 do

     a:=a+1;  (6 раз, а=6)

2. Чему равно значение a,b?

  a:=5; b:=6;

a:=b;

b:=a;  (а=6, b=6)

 Задача поменять значения переменных a,b. Как это сделать?

  (c:=a;  a:=b; b:=c;)

3. Дан числовой массив  A:  12    9    -1   4   47   20   -10. Ответить на вопросы:

• Назовите размерность массива.  
• Назовите индексы нечетных элементов.
• Найдите a[3]+a[7].
• Найдите максимальный элемент и его индекс.

3. Формулировка темы и постановка целей урока.

 Дан символьный массив (список фамилий).

Найдите индекс элемента с фамилией вашего соседа по парте.

В чем заключалась сложность выполнения этого задания? (Фамилии расположены  не по алфавиту, не упорядочены). В каком порядке можно расставлять элементы? (В алфавитном). А числовые массивы? (В порядке возрастания или убывания).

Тема нашего урока «Сортировка массива». Какаие задачи необходимо решить в течение урока?

- Изучить понятие сортировка;

- Познакомиться с методами сортировки;

- Составить программу на языке Pascal, реализующую сортировку одномерного массива.

4. Объяснение нового материала.

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

Зачем сортировать данные? (Сортировка главным образом нужна, для того чтобы ускорить поиск).

Методы сортировки:

Существующие методы сортировки  можно разделить на две группы:

- простые, но медленно работающие (особенно на больших массивах);

- сложные, но быстрые, дающие колоссальный выигрыш на больших массивах.

содержащих тысячи элементов,

Смоделируем ситуацию. Перед вами пять книг разной толщины. Можно ли их назвать моделью массива? (Да. Отвечают определению массива).

Берем первую книгу. Будем сравнивать ее со всеми остальными. Если порядок возрастания нарушается, то произведем перестановку. Продемонстрировать сортировку полностью. Этот метод называется пузырьковым.

Сформулируем алгоритм:

1) Зафиксировать элемент массива.

2) Сравнивать зафиксированный элемент со всеми последующими.

     Если порядок возрастания нарушен, то произвести перестановку.

3) Пункты 1), 2) повторить для всех элементов кроме последнего.

Составим программу. (Для экономии места и времени блоки ввода и вывода массива пропускаются, учениками заполняются самостоятельно. При написании программы учитель комментирует операторы).

program Sort;

  const n=10;

  var a:array[1..n] of  integer;

       i,j,c: integer;

  begin

    {ввод массива}

    for i:=1 to n-1 do

      for j:=i+1 to n do

         if a[i]>a[j] then

          begin

             c:=a[i];

             a[i]:= a[j];

            a[j]:=c;

         end;

     {вывод массива}

end.

Заполним по данной программе трассировочную таблицу:

Почему этот метод назван пузырьковым? (После каждого прохода по массиву «наверх» поднимаются самые «легкие» элементы).

Сколько раз произведена перестановка элементов? Сколько сравнений было произведено? Ребята, вы можете назвать недостаток данного алгоритма? (Массив фактически отсортирован, а алгоритм продолжает работать).  Как можно было бы его улучшить?

(Ввести переменную-флажок, по которой можно было определять, производилась внутри цикла перестановка).

Вместе с учащимися составляется программа сортировки с флажком.

program SortF;

  const n=10;

  var a:array[1..n] of  integer;

       i,k,c: integer;

  begin

    {ввод массива}

  repeat

    k:=0;

    for i:=1 to n-1 do

         if a[i]>a[i+1] then {сравнение попарно}

          begin

             c:=a[i];

             a[i]:= a[i+1];

            a[i+1]:=c;

         end;

  until k=0;

     {вывод массива}

end.

Какие еще методы сортировки можете предложить, использую известные вам алгоритмы? (Алгоритмы поиска минимального или максимального элемента массива). Это  метод называется методом выбора. 

Данные методы сортировки для больших массивов (более 1000 элементов) работают медленно. Один из самых популярных «быстрых» методов, разработанный в 1960 году Чарльзом Хоаром, так и называется – «быстрая сортировка».

Пусть дан массив А из n элементов. Выберем сначала наугад любой элемент массива (Х). Обычно выбирают средний элемент. На первом этапе расставляются элементы таким образом:

Далее отсортировывается каждая часть массива отдельно.

Сравним методы сортировки:

Как показывают эти данные, преимущество быстрой сортировки становится подавляющим при увеличении N.

5. Закрепление изученного материала.

Реализуем данный алгоритм за компьютерами.

Учащиеся работают за компьютерами.

6. Подведение итогов урока.

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

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

1) Прочитать п. 64 учебника (К.Ю. Поляков, Е.А. Еремин Информатика 10 класс)

2) Составить  трассировочную таблицу метода пузырька для 7 элементов

3) Составить трассировочную таблицу метода пузырька с флажком для 7 элементов.

4) Составить программу сортировки методом выбора.

 (Задания 2-4 по выбору учащихся)

Спасибо за урок.