Конспект урока по информатике на тему:

«Сортировки массивов: обменная и выбором»

Тема: «Сортировки массивов: обменная и выбором»

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

Цели:

- обучающие – знакомство с методами сортировки элементов массива.

- развивающие – развитие навыков решения задач и применения аглоритмов.

- воспитывающие – аккуратность записи данных в тетради.

Формируемые знания и умения:

         Ученик:

         должен знать:

- Запись массивов;

- Основные операции с массивом;

- Ввод и вывод массива; обработка массива;

         должен уметь:

 - Решать задачи с помощью массивов;

 - Применять алгоритмы сортировки.

Формы и методы: Лекция с элементами беседы, решение задач.

Оборудование: компьютер,  проектор.

Литература:

1. Информатика. Базовый курс. 7-9 классы / И.Г.Семакин, Л.А. Заголова, С.В.Русаков, Л.В.Шестаков.-2-е изд., испр. И доп.- М.:БИНОМ. Лаборатория знаний, 2004.
2. 2.                     Методика преподавания информатики: Учеб. Пособие для студентов Пед. Вузов / М.П. Лапчик, И.Г. Семакин, Е.К.Хеннер; Под общей ред. М.П. Лапчик.- М.: «Академия», 2001. 

 План урока

1. Орг. момент    2 мин
2. Объяснение нового материала        40 мин
3. Подведение итогов, задание на дом    3 мин

Согласовано                                                     

Учитель:_________/Рязанова Т.В./

Методист:_______/Пихтовников. С.В/

Ход урока.

Учитель:  Здравствуйте, ребята. Запишите число и тему сегодняшнего урока: «Сортировки массивов: обменная и выбором». Цель нашего урока изучить алгоритмы сортировки.

Давайте вспомним, что такое массивы?

Ученики:   Массив – это структурированный тип данных, состоящий из фиксированного числа элементов, имеющих один и тот же тип.

Учитель: Совершенно верно, теперь перечислите 5 основных действий с массивом.

Ученики:

1. Ввод массива.
2. Вывод массива
3. Поиск в массиве
4. Обработка массива
5. Сортировка массива

Учитель:   Верно, а сегодня мы рассмотрим пятый пункт «Сортировка массива». Так что же такое сортировка?

В тетрадь

Сортировкой называется распределение элементов массива в соответствии с определенными правилами.

Например,  сортировка файла, содержащего фамилии, в алфавитном порядке, сортировка массива чисел по возрастанию или убыванию и т.д.

Ученики:  (записывают)

Учитель: Вы когда-нибудь задумывались почему, например, слова в словаре расположены по алфавиту?

Ученики: 

Учитель: Правильно сортировка главным образом нужна, для того чтобы ускорить поиск. А давайте подумаем, если бы слова были расположены в случайном порядке, как бы сильно увеличилось время поиска нужного слова.

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

Учитель: Мы с вами будем говорить о сортировке чисел.

Пример сортировки чисел.

5 2 3 7 1 => 7 5 3 2 1

Как называется такая сортировка?

Ученики:  По убыванию.

Учитель: Как будет выглядеть этот же массив, отсортированный по возрастанию?

Ученики: 1 2 3 5 7

Учитель: Существует много способов сортировки. Сегодня, мы с вами рассмотрим два вида сортировки: выбором и пузырьком.

Учитель: Рассмотрим сортировку выбором. Запишите заголовок – Сортировка Выбором. 

 Например, дан массив A, нужно отсортировать по возрастанию:

1. 1.     Находим номер  m минимального элемента массива; 
2. 2.     Меняем местами i-ый и m-ый элементы массива.  
3. 3.     Выполнить пункты 1 и 2 для следующих элементов, без i-го элемента. 

Пункт 3 повторять, пока остаток массива не сократится до одного элемента. 

Зарисуйте таблицу и запишите порядок действий.

Ученики: (выполняют).

Учитель: Теперь запишем наши действия на языке Pascal.

При работе с массивами всегда используем циклы. Будем использовать циклы с параметром (for), как выглядит синтаксис?

Ученики: for i:=1 to n do begin …end;

Учитель: Для нахождения минимального элемента нам понадобится алгоритм поиска минимума, который мы знаем. И при этом нужно так же запомнить номер этого минимума. Вспомним как найти минимум.

Ученики:

         for j:=1 to n do

         if a[j]<=min then begin  m:=j;  min:=a[j];  end;

Учитель: Так как нам нужно находить номер минимума m для последующих оставшихся элементов, согласно нашей таблице, то придется использовать вложенные циклы. То есть цикл для поиска минимума мы должны вложить в цикл обработки массива, где мы заменяем m-ый элемент с текущим i-ым. Причем во вложенном цикле параметр j принимает значения от i до n, для того чтобы не задевать уже отсортированные элементы.

Во внешнем цикле произведем перестановку элементов, для замены будем использовать вспомогательную переменную p.

Конечная запись примет вид:

(алгоритм сортировки выбором)

for i:=1 to n do begin                       

  min:=a[i];

        for j:=i to n do                          {цикл нахождения номера минимума}

         if a[j]<=min then

               begin  m:=j;  min:=a[j];  end;

  p:=a[i];                                          {перестановка элементов }

  a[i]:=a[m];

  a[m]:=p;

end;

Запишите  данный алгоритм в тетрадь.

Ученики:  (записывают).

Учитель:

Учитель: Теперь, рассмотрим сортировку обменом (методом пузырька). Запишите – Сортировка  пузырьком (обменом).

Принцип сортировки:

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

Например, необходимо отсортировать массив по возрастанию.

Запишите принцип сортировки и зарисуйте таблицу.

Ученики:  (записывают)

Учитель: Согласно нашей схеме при каждом проходе сравниваем поочередно пару элементов. Элементы, которые не удовлетворяют условию, меняются местами. Затем опять проверяется пара элементов и так далее. Поэтому самый большой «всплывает» вверх. Но одного прохода недостаточно, нужно еще сделать сортировку, пока очередной проход не вызовет ни одного обмена. Тем самым, последний проход исполняет роль проверки.

Далее опишем нашу сортировку на Pascal, с помощью цикла repeat.

Как записывается цикл с пост условием(repeat)?

Ученики:  Repeat <тц> until (условие);

Учитель: Нам также понадобятся вложенные циклы, вложенный цикл (For) будет отвечать за попарную перестановку элементов, а внешний (Repeat) – за проходы по массиву.

Разберем внутренний цикл перестановки, удобнее использовать цикл с параметром. Параметром, которого будет i, принимающее значение количества пар элементов. Как вы думаете, сколько будет пар в массиве размерности 6, 10, n?

Ученики:  5, 9, n-1.

Учитель: Тем самым в цикле будем сравнивать a[i] элемент и последующий a[i+1].

Какое условие нужно записать в ветвлении для сравнения?

Ученики:  a[i] > a[i + 1]  

Учитель: Если a[i] больше, то его меняем местами с a[i+1]. Для перестановки нам так же понадобится вспомогательная переменная P. Как запишется наша перестановка?

Ученики:   p:= a[i];                                 

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

a[i + 1]:= p;

Учитель: Так как проходы с перестановками будут выполняться до тех пор, пока число перестановок не станет равно нулю, мы должны во внешнем цикле ввести условие завершения цикла until k=0. Где k – количество перестановок.

При каждом новом проходе мы должны этот счетчик обнулять. А во вложенном цикле For должны подсчитать количество перестановок.

Как вы думаете, как можно подсчитать количество k?

Ученики:  k:=k+1;

Учитель: Итак, как думаете, выглядит внутренний цикл перестановок?

Ученики:  For i:= 1 To n-1 Do                               

                    If a[i] > a[i + 1] Then                         

Begin

p:= a[i];                                 

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

a[i + 1]:= p;                                                 

k:=k + 1;                                      

End;

Учитель: Если же при каком-нибудь очередном проходе цикла repeat, k останется равно нулю, то цикл завершится. В итоге наша запись в Паскале примет такой вид:

  (алгоритм сортировки пузырьком)                                              

    Repeat             {До тех пор, пока число перестановок не станет равно нулю,}

       k:= 0;                                                       {начинаем новый проход по массиву.}

       For i:= 1 To n-1 Do                               {Рассматриваем n-1 пару элементов.}

                    If a[i] > a[i + 1] Then                          {Если пара стоит не на месте,}

Begin

p:= a[i];                                  {меняем элементы местами и}

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

a[i + 1]:= p;                                                  { указываем, что}

k:=k + 1;                                       {перестановка произошла.}

End;

    Until k = 0;

Запишите данный фрагмент в тетрадь.

Ученики:  (записывают).

Учитель: Подведем итоги, мы рассмотрели два типа сортировки выбором и пузырьком.

Есть ли у вас вопросы по данной теме? Какие ситуации вам нужно прояснить?

Ученики: (задают вопросы).

Учитель: Применяя их можно успешно отсортировать массивы чисел. Ваша задача запомнить их и научится применять на практике. Подготовиться к решению задач лабораторных работ.