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

Урок по теме: «Сортировка одномерных массивов»

Иванова С.Ю. учитель информатики и ИКТ

Цели урока: 

1. Образовательная: ознакомление учащихся с понятием сортировки, с методами сортировки; формирование у учащихся навыков составления алгоритмов сортировки и применение этих методов в программах.
2. Развивающая: Развитие алгоритмического мышления; умения применять полученные знания при решении задач различной направленности.
3. Воспитательная: привитие учащимся навыков самостоятельности в работе; воспитание чувства ответственности.

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

Методы обучения: наглядный, объяснительно-иллюстративный,  частично-поисковый, практический.

Средства обучения: 

• Технические: компьютеры, проектор.
• Программные: ЯП Турбо Паскаль, Презентации по теме «Сортировка одномерных массивов»(часть 1, часть 2).

Продолжительность урока:  90 мин.

План урока:

Ход урока:

1. Учитель: Тема сегодняшнего урока - Сортировка одномерных массивов. Сегодня на уроке мы познакомимся с понятием сортировки, узнаем, какие существуют методы сортировки, научимся использовать эти методы в программах. (Учащиеся записывают тему в тетрадь, цели урока демонстрируются в презентации).

2. Учитель: Для начала нам необходимо вспомнить, что такое массив, какими способами можно его задать, как описать массив в программе, как обратиться к элементу массива, как можно использовать функцию random. (два ученика отвечают у доски, один или несколько - с мест устно).

3. 3.1. Учитель: Сортировка - один из наиболее распространенных процессов современной обработки данных, например: списки учащихся в классном журнале, фамилии в телефонном справочнике, книги -  в библиотеке и т.д..  Сортировку можно определить как размещение     некоторых объектов в определенном порядке их значений:     по возрастанию или убыванию (когда сортируемыми элементами      являются числа), или в алфавитном порядке (при сортировке     текстовой информации).

     Под сортировкой массива подразумевается процесс перестановки элементов с целью упорядочивания их в соответствии с каким-либо критерием. Например, если имеется массив целых a , то после сортировки по возрастанию должно выполняться условие:

a [1] <= a [2] <= … <= a [n]

n- верхняя граница индекса массива.

(Учащиеся записывают определение сортировки  в тетрадь. Текст определения в презентации).

Задача сортировки распространена в информационных системах и используется как предварительный этап задачи поиска, поскольку поиск в упорядоченном (отсортированном) массиве проводится намного быстрее, чем в неупорядоченном.

Существует достаточно много методов (алгоритмов) сортировки массивов. Мы с вами рассмотрим два наиболее распространенных метода – метод прямого выбора и метод простого обмена. Вам будут продемонстрированы оба метода на примере числовых массивов. Ваша задача – определить алгоритм сортировки обоих методов.

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

Учитель: Кто может сформулировать алгоритм метода прямого выбора? (Некоторые учащиеся пытаются сформулировать алгоритм, учитель помогает, затем все записывают алгоритм в тетрадь, на экране дублируется текст алгоритма. (Презентация – теоретическая часть)).

Алгоритм сортировки:

1. Просмотреть массив, начиная от первого элемента, найти минимальный элемент и поместить его на место первого элемента, а первый – на место минимального.
2. Просмотреть массив, начиная от второго элемента, найти минимальный элемент и поместить его на место второго элемента, а второй – на место минимального и т.д., пока не будет отсортирован весь массив.

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

Давайте запишем фрагмент программы, который позволяет отсортировать массив методом прямого выбора. (Демонстрируется презентация (часть 2). Учащиеся делают запись в тетрадь, учитель подробно объясняет действие циклов).

…for i:=1 to n-1 do

       begin

         min:=i;

         for j:=i+1 to n do

         if a[j]

         c:=a[min];

         a[min]:=a[i];

         a[i]:=c;

      end;

…

3.2. Учитель: Рассмотрим  второй метод сортировки – сортировка  простым обменом («пузырьковая»).

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

Алгоритм сортировки:

1. Последовательно сравниваются пары соседних элементов массива. Если первый элемент пары оказался больше второго, то они меняются местами и на первое место (как пузырек) «всплывает» меньший из двух элементов.
2. Операция повторяется для оставшихся элементов и т.д.

Учитель: Алгоритм также использует вложенные циклы. В отличие от первого алгоритма, внутренний цикл находит наименьший элемент из двух соседних и осуществляет перестановку в случае, если второй элемент оказался меньше первого.

(Учащиеся записывают фрагмент программы.)

…for i:=1 to n-1 do

  for j:=1 to n-1 do

   if a[j]>a[j+1] then

    begin

       c:=a[j];

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

       a[j+1]:=c;

    end;

…

4.Учитель: Мы научились сортировать массивы по возрастанию. Ваша задача – изменить алгоритмы и команды в программах так, чтобы сортировка происходила по убыванию, т.е. чтобы а[1]>=a[2]>=…>=a[n].

Задача 1. Задать массив из 5 элементов методом простого ввода.

Отсортировать элементы массива по убыванию методом прямого выбора.

(Учащиеся садятся за компьютеры и решают задачу. Учитель просматривает решения и корректирует действия учащихся по мере необходимости.)

Задача 2. Задать массив из 10 элементов случайным образом из отрезка[-10;20]. Отсортировать элементы массива по убыванию методом простого обмена («пузырек»).

Задача 3. Определить самый холодный и самый теплый день за прошедшую неделю. 

Задача 4. Дан одномерный массив из 10 элементов. Элементы задаются случайным образом из интервала [-20;20]. Осуществить сортировку четных элементов массива методом прямого выбора.

5.  Учитель: Итак, сегодня на уроке мы узнали о том, что все элементы массива можно упорядочивать в соответствии с каким-либо критерием. Вы так же узнали, что существуют различные способы сортировки: (ученики еще раз перечисляют методы сортировки и их алгоритмы). Учитель выставляет оценки за урок.

Домашнее задание: а) выучить теоретический материал (определение и методы сортировки, алгоритмы и их реализация в программах);

б) Задача. Имеются два одномерных массива целых чисел размера n. Создать из них один одномерный массив, в котором сначала идут отрицательные элементы, затем нулевые и затем положительные. (Ключ – соединить два массива в один, а затем упорядочить полученный массив, используя «пузырьковый» метод сортировки.)

Приложения:

1. Решение заданий, предлагаемых ученикам на уроке.

Задача 1.

 Const n=5;

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

             i,j,max:integer;

  begin

   writeln(‘Введите 5 элементов массива’);

        for i:=1 to n do

         read(a[i]);

    Writeln;

     For i:=1 to n-1 do

       begin

         max:=i;

         for j:=i+1 to n do

         if a[j]>a[max] then max:=j;

         c:=a[max];

         a[max]:=a[i];

         a[i]:=c;

      end;

  writeln(‘Отсортированный массив по убыванию методом выбора:’);

      For i:=1 to n do

          write(a[i]:4);  

End.

Задача 2.

   Const n=10;

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

             i,j,c:integer;

  begin

randomize;

writeln(‘Исходный массив:’);

   For i:=1 to n do

      begin

       a[i]:=random(31)-10;

       write(a[i]:4)

       end;

   Writeln;

   For i:=1 to n-1 do

        For j:=1 to n-1 do

          if a[j]

            begin

              c:=a[j];

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

              a[j+1]:=c;

           end;

writeln(‘Отсортированный массив по убыванию методом обмена:’);

     For i:=1 to n do

        write(a[i]:4)

End.

Задача 3. Ключ - создать массив из 7 элементов способом простого ввода. Отсортировать массив любым методом по возрастанию. Вывести на экран первый и последний элементы как самый холодный и самый теплый день соответственно. (Элементы не должны повторяться.)

Задача 4. Ключ – при сортировке необходимо проверять условии четности элемента массива (if a[i] mod 2 =0 then…).

2. Решение домашней задачи.

 Const n=10;

  Var a,b: array [1..n] of integer;

            c: array [1..2*n] of integer; i,j,k:integer;

  begin

    randomize;

    for i:=1 to n do

      begin a[i]:=random(20)-5; b[i]:=random(10)-3 end;

    writeln(‘Массив А’);

     for i:=1 to n do

         write(a[i]:4);

       writeln;

       writeln(‘Массив В’);

       for i:=1 to n do

         write(b[i]:4);

      writeln;

         for i:=1 to n do

          c[i]:=a[i];

       k:=1;

         for i:=n+1 to 2*n do

           begin

             c[i]:=b[k];

              ink(k)

           end;

       for i:=1 to 2*n-1 do

        for j:=1 to 2*n-1 do

          if c[j]>c[j+1] then

           begin

             k:=c[j]; c[j]:=c[j+1]; c[j+1]:=k

          end;

     writeln(‘Массив С’);

           for i:=1 to 2* n do

         write(c[i]:4);

writeln

End.