Урок по теме "Сортировка массива"

Урок по теме "Сортировка массивов методом «пузырька»"

Клокова Ольга Михайловна, учитель информатики МБОУ Лицей «Дубна»

Цели урока:

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

Развивающая: развитие алгоритмического мышления; умения применять полученные знания при решении задач различной направленности.

Воспитательная: привитие учащимся навыков самостоятельности в работе.

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

Вид урока: урок-практикум.

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

Формы обучения: коллективная.

Технологии: личностно-ориентированная, игровая.

Оборудование: компьютеры, программное обеспечение – Linux, среда программирования Geany для написания программы на языке Паскаль.

Ход урока

I. Сообщение темы и постановка целей урока.

II. Актуализация опорных знаний учащихся.

Устный опрос:
Как описать числовой массив в программе?

Как описать массив строковых переменных в программе?

Как задаётся массив в разделе описания констант?

Как осуществить ввод массива с клавиатуры?

Как осуществить ввод массива с помощью генератора случайных чисел?

III. Ознакомление с новым материалом.

Сортировка – один из наиболее распространенных процессов обработки данных.

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

Например, массив Х из N элементов будет отсортирован в порядке возрастания значений его элементов, если Х[1] ≤ Х[2] ≤… ≤ Х[N], и в порядке убывания, если Х[1] ≥ Х[2] ≥… ≥ Х[N].

Сортировка символьного массива заключается в расположении элементов, например, по алфавиту или по длине строк.

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

Метод обмена или метод «пузырька».

Сортировка пузырьковым методом является наиболее известной. Её популярность объясняется запоминающимся названием и простотой алгоритма, в основе которого лежит обмен соседних элементов массива. Каждый элемент массива, начиная с первого, сравнивается со следующим и если он больше следующего, то элементы меняются местами. Таким образом, элементы с меньшим значением продвигаются к началу массива (всплывают), а элементы с большим значением – к концу массива (тонут), поэтому этот метод иногда называют методом “пузырька”. Название обусловлено подобием процессу движения пузырьков в резервуаре с водой, когда каждый пузырёк находит свой собственный уровень. Этот процесс повторяется на единицу меньше раз, чем элементов в массиве.

Рассмотрим процесс упорядочивания элементов массива по возрастанию в игровой форме.

Один учащийся заполняет таблицу следующего вида на доске.

	№ элемента
	1	2	3	4	5
Исходный массив	7	3	5	4	2
1-ый просмотр
2-ой просмотр
3-ий просмотр
4-ый просмотр

Пять учащихся выстраиваются в линию, им раздаются карточки с цифрами: 7, 3, 5, 4, 2 (они будут представлять собой элементы массива). По ходу объяснения учащиеся демонстрируют, как происходит перестановка элементов в массиве, и каждый просмотр фиксируется на доске. В результате, заполненная таблица должна выглядеть следующим образом.

	№ элемента
	1	2	3	4	5
Исходный массив	7	3	5	4	2
1-ый просмотр	3	5	4	2	7
2-ой просмотр	3	4	2	5	7
3-ий просмотр	3	2	4	5	7
4-ый просмотр	2	3	4	5	7

В рабочие тетради учащиеся зарисовывают полученную таблицу и записывают описание метода «пузырька».

При методе «пузырька» сравнивается 1-ый элемент со 2-ым. Если 1-ый окажется больше 2-го, то их поменяем местами. Те же действия выполним для 2-го и 3-го, 3-го и 4-го,…, (n-1)-го и n-го элементов. В результате этих действий самый большой элемент станет на последнее (n-е) место. Затем алгоритм повторяется сначала, но n-ый элемент не рассматривается. Так повторяют, пока не упорядочат весь массив.

Рассмотрим блок-схему представленного алгоритма. Блок-схема рисуется на доске, внимание учащихся акцентируется на том, что здесь мы должны использовать вложенный цикл, так как просмотр элементов массива осуществляется несколько раз. Блок для перестановки элементов, задействующий вспомогательную переменную, заполняется с помощью учащихся. Им предлагается вспомнить, как поменять местами значения двух переменных.

…

 

…

IV. Закрепление нового материала.

Работа с карточками.

Учащимся раздаются карточки, которые они должны заполнить.

1 вариант

Выполнить сортировку массива методом пузырька.

Исходный массив	Номер элемента					Метод
	1	2	3	4	5
	25	20	24	23	10
1 просмотр						Пузырёк
2 просмотр
3 просмотр
4 просмотр

2 вариант

Выполнить сортировку массива методом пузырька         

Исходный массив	Номер элемента					Метод
	1	2	3	4	5
	34	30	33	32	16
1 просмотр						Пузырёк
2 просмотр
3 просмотр
4 просмотр

3 вариант

Выполнить сортировку массива методом пузырька                  

Исходный массив	Номер элемента					Метод
	1	2	3	4	5
	44	20	33	27	18
1 просмотр						Пузырёк
2 просмотр
3 просмотр
4 просмотр

4 вариант

Выполнить сортировку массива методом пузырька                  

Исходный массив	Номер элемента					Метод
	1	2	3	4	5
	14	20	18	15	7
1 просмотр						Пузырёк
2 просмотр
3 просмотр
4 просмотр

ОТВЕТЫ

1 вариант

Исходный массив	Номер элемента					Метод
	1	2	3	4	5
	25	20	24	23	10
1 просмотр	20	24	23	10	25	Пузырёк
2 просмотр	20	23	10	24	25
3 просмотр	20	10	23	24	25
4 просмотр	10	20	23	24	25

2 вариант

Исходный массив	Номер элемента					Метод
	1	2	3	4	5
	34	30	33	32	16
1 просмотр	30	33	32	16	34	Пузырёк
2 просмотр	30	32	16	33	34
3 просмотр	30	16	32	33	34
4 просмотр	16	30	32	33	34

3 вариант

Исходный массив	Номер элемента					Метод
	1	2	3	4	5
	44	20	33	27	18
1 просмотр	20	33	27	18	44	Пузырёк
2 просмотр	20	27	18	33	44
3 просмотр	20	18	27	33	44
4 просмотр	18	20	27	33	44

4 вариант

Исходный массив	Номер элемента					Метод
	1	2	3	4	5
	14	20	18	15	7
1 просмотр	14	18	15	7	20	Пузырёк
2 просмотр	14	15	7	18	20
3 просмотр	14	7	15	18	20
4 просмотр	7	14	15	18	20

Задача

Составить программу сортировки массива из N элементов по возрастанию методом обмена по представленной блок-схеме. Массив задать случайными числами из диапазона [0-25], N взять равным 10. Вывести на экран исходный и отсортированный массивы.

Примерный код программы.

program SortPuzir;                                                           

const n=10;                                                                    

var i,j,b:integer;                                                         

    A:array[1..n] of integer;                                              

begin                                                                        

    randomize;

    for i:=1 to n do begin                                                   

        A[i]:=random(26);                                                    

        write(A[i]:5);                                                       

    end;                                                                      

    writeln;                                                                 

    for j:=1 to n-1 do begin                                                 

    for i:=1 to n-j do begin                                                 

    if A[i]>A[i+1] then                                                      

       begin                                                                  

         b:=A[i];                                                            

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

         A[i+1]:=b;                                                          

       end;                                                                  

    end;                                                                      

    end;                                                                     

    writeln;

    for i:=1 to n do write(A[i]:5);                                           

end.                                                                        

Вопрос: Что нужно изменить в программе, чтобы выполнялась сортировка массива по убыванию?

V. Самостоятельная работа учащихся за компьютером.

Учащимся предлагаются задания трех уровней сложности.

Уровень 1.

На соревнованиях по прыжкам в длину получен массив b(n). Определить три лучших результата. Массив сформировать с помощью генератора случайных чисел.

Уровень 2.

Заданы два массива одинаковой размерности (строковый и числовой). Элементы строкового массива представляют собой фамилии учащихся (задаётся в разделе описания констант), а числовой массив представляет собой баллы полученные на ЕГЭ (генератор случайных чисел – диапазон [1-100]). Между элементами 2-х массивов однозначное соответствие: фамилии 1-го элемента из строкового массива соответствуют баллы 1-го элемента числового и т.д. Вывести исходные массивы в виде: Фамилия – баллы, а затем массивы отсортированные по убыванию полученных баллов.

Уровень 3.

Решить задачу (Уровень 2), оптимизировав её таким образом, что если после очередного прохода по числовому массиву ни разу не произошла перестановка элементов, это значит, что массив уже отсортирован и можно завершать выполнение программы.

VI .Проверка работ учащихся. Подведение итогов урока, выставление оценок.

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

Выучить материал по конспекту и п.1.7.7 Алгоритмы сортировки данных стр.158-163 учебник Семакин И.Г. 10 класс.