Тема урока «Сортировка массива»
Цель урока: Дать определение сортировки, сформировать умение определять вид массива, отработать навык упорядочения массива.
План урока
- Актуализация знаний (тест) Объяснение нового материала Закрепление нового материала Практическая работа Домашнее здание
Ход урока
Тестирование учащихся, с целью выяснения уровня знаний 10 мин.
Новый материал.
Для решения многих задач удобно сначала упорядочить данные по определенному признаку, так можно ускорить поиск некоторого объекта. Например, в преферансе игроки раскладывают карты по мастям и по значению. Так легче определить, каких карт не хватает. Или возьмем любой энциклопедический словарь - статьи в нем упорядочены в алфавитном порядке. При заполнении классного журнала, тоже удобнее записывать в алфавитном порядке фамилии. При построении на урок физкультуры удобнее выстраивать по росту. И т. Д.
Перегруппирование заданного множества объектов в определенном порядке называют сортировкой.
Почему сортировке уделяется большое внимание? Вы также это поймете, прочитав цитаты двух великих людей.
"Даже если бы сортировка была почти бесполезна, нашлась бы масса причин заняться ею! Изобретательные методы сортировки говорят о том, что она и сама по себе интересна как объект исследования." /Д. Кнут/
"Создается впечатление, что можно построить целый курс программирования, выбирая примеры только из задач сортировки." /Н. Вирт/
Отличительной особенностью сортировки является то обстоятельство, что эффективность алгоритмов, реализующих ее, прямо пропорциональна сложности понимания этого алгоритма. Другими словами, чем легче для понимания метод сортировки массива, тем ниже его эффективность.
Сегодня существует множество методов сортировки, но для понимания сути сортировки рассмотрим некоторые из них.
Сортировка — один из наиболее распространенных процессов современной обработки данных. Сортировкой называется распределение элементов множества по группам в соответствии с определенными правилами.
Самыми распространенными являются сортировки по убыванию и возрастанию.
Например, сортировка элементов массива, в результате которой получается массив, каждый элемент которого, начиная со второго, больше стоящего от него слева, называется сортировкой по возрастанию. В обратном порядке по убыванию. Если не все элементы различны, то надо говорить о неубывающем (или невозрастающем) порядке.
Существует несколько методов сортировки массива: сортировка отбором (линейная), сортировка методом пузырька, метод быстрой сортировки с разделением (метод К. Хоора) , сортировка массива методом перестановок и т. д. Все эти методы мы рассматривать мы не будем, за неимением времени, остановимся только на простейших.
Критерии оценки эффективности алгоритмов сортировки могут включать следующие параметры:
- количество шагов алгоритма, необходимых для упорядочения; количество сравнений элементов; количество перестановок, выполняемых при сортировке.
Сортировка методом пузырька
Одним из самых популярных методов сортировки – «пузырьковый» метод основан на том, что в процессе исполнения алгоритма более легкие элементы массива постепенно «всплывают». Особенностью данного метода является сравнение не каждого элемента сов семи, а сравнение в парах соседних элементов. Алгоритм пузырьковой сортировки по убыванию состоит в последовательных просмотрах снизу вверх (от начала до конца) массива. Если соседние элементы таковы, что выполняется условие, согласно которому элемент справа больше элемента слева, то выполняется обмен значениями этих элементов.
Метод "пузырька" является самым простым методом сортировки. Чтобы уяснить его идею, представьте, что массив (таблица) расположен вертикально. Элементы с большим значением всплывают вверх наподобие больших пузырьков. При первом проходе вдоль массива, начиная проход "снизу", берется первый элемент и поочередно сравнивается с последующими. При этом:
если встречается более "легкий" (с меньшим значением) элемент, то они меняются местами;
при встрече с более "тяжелым" элементом, последний становится "эталоном" для сравнения, и все следующие сравниваются с ним.
В результате наибольший элемент оказывается в самом верху массива.
Применение метода "пузырька" можно проследить запустив программу Сортировки.1
Но прежде чем перейти к рассмотрению конкретного алгоритма той или иной сортировки немного вспомним материал, который пригодится нам в дальнейшем.
Задача №1. Даны две целочисленные переменные х и y. Составить фрагмент программы, после выполнения которого значения этих переменных распределяются в порядке убывания.
Обмен значений переменных нужно производить лишь в том случае, если х<у. Для того чтобы не потерять начальное значение переменной х, введем дополнительную переменную t.
(ученик у доски записывает решение)
if x<y then
begin
t:=x;
x:=y;
y:=t;
end;
Задача №2. Составить фрагмент программы поиска максимального числа из трех введенных с клавиатуры чисел.
Пусть а, b, c - вводимые с клавиатуры числа, Max - максимальное из их значений. На первом шаге предположим, что а - максимальное из чисел и поэтому Max:=a. Затем сравним значение предполагаемого максимума со значениями переменных b и с. Если значение Max окажется меньше, чем значение очередной переменной, то переопределим значение максимума.
. m:=a;
if m<b then
m:=b;
if m<c then
m:=c;
. . .
Задача №3. Дан массив а, состоящий из 10 элементов. Составить программу поиска максимального элемента массива.
Используем идею предыдущей задачи. Перед началом поиска выберем условно в качестве максимального первый элемент массива Max:=a[1]. Затем по очереди каждый элемент массива сравним со значением переменной m. Если он окажется больше, то изменим значение Max. После анализа всех элементов массива переменная Max содержит значение максимального элемента массива.
Max:=a[1];
for i := 2 to 10 do
if Max<a[i] then
Max := a[i];.
- Теперь можно привести текст программы упорядочения массива M[1..N]: For j = 1 To N - 1 For i = 1 To N - j If m(i) > m(i + 1) Then t = m(i) m(i) = m(i + 1) m(i + 1) = t End If Next i
Next j
Задача 1. Дан список класса из 30 учеников, отсортировать его по алфавиту. Данная задача аналогична следующей:
Дан строковый массив. Упорядочить его элементы в порядке возрастания.
Private Sub Command1_Click()
'program Sortirovka;
Dim N, I, J As Integer
Dim a(1 To 30) As String
Dim t As String
N = InputBox("Введите количество элементов: ", "")
For I = 1 To N
a(I) = InputBox("Введите фамилию", "")
Next I
For j = 1 To N-1
For i = 1 To N-j
If a(i)<=a(i+1)Then
t = a(I)
a(I) = a(i+1)
a(i+1) = t
Next I
Next J
For I = 1 To N
Print a(I); " ";
Next I
End Sub
Задача №2
- Дан список, в котором указаны роста участников команд. Отсортируйте от меньшего к большему. Данная задача аналогична следующей: Дан целочисленный массив. Упорядочить его элементы в порядке возрастанию. Решение 1.Описание массива и величин Имя массива m количество элементов 30 Тип byte Промежуточная величина t – byte, индекс I, j-byte 2. Ввод Случайным образом m(i)=int(rnd()*100) 3. Сортировка по возрастанию методом «пузырька»
4.Вывод
- 'program Sortirovka; Dim N, I, J, K As Integer Dim a(1 To 30) As byte Dim t As byte N = Input Box("Введите количество элементов: ", "")
- For I = 1 to N m(I) = int(rnd()*100) Print m(i) Next I Print For j = 1 To N – 1 For i= 1To N-j If m(i) > m(i + 1) Then t = m(i) m(i) = m(i + 1) m(i + 1) = t End If Next i Next j For I = 1 To N Print m(I); " "; Next I End Sub
Линейная сортировка (сортировка отбором)
Идея линейной сортировки по возрастанию заключается в том, чтобы, последовательно просматривая весь массив, отыскать наименьшее число и поместить его на первую позицию, обменяв его с элементом, который ранее занимал первую позицию. Затем просматриваются все остальные элементы массива и выполняется аналогичная операция по отбору из рассматриваемой части массива минимального элемента и обмену местами этого элемента и первого в рассматриваемой части и т. д.
Сортировка массива по возрастанию методом перестановок. Идея алгоритма сортировки по возрастанию массива, состоящего из N элементов, методом перестановок элементов, состоит в последовательном поиске минимальных элементов и их перемещении к началу массива с помощью перестановок с элементами, имеющими меньший индекс.
Рассмотрим этот метод. На первом шаге находим минимальный элемент массива и меняем его местами с первым элементом массива. Остаются неупорядоченными N-1 элемент. Проводим поиск минимального элемента среди элементов со 2 по N-1 и делаем перестановку.
Повторяем процедуру поиска минимального элемента среди оставшихся неупорядоченных элементов многократно. Повторение реализуем с помощью цикла со счетчиком, максимальное значение которого составляет N-1. В результате массив сортируется по возрастанию.
Закрепление материала
Ученик отвечает тест на компьютере у доски, а остальные устно отвечают на вопросы.
- Ответьте на вопросы В каком виде отсортирован массив:
- Что такое сортировка? Какие способы сортировки Вы знаете? Для чего необходима сортировка?
Практическая работа
Упражнение 1
Запустите интегрированную среду программирования. Введите текст программы Sortirovka и запишите файл на диск под соответствующим именем. Несколько раз запустите программу на исполнение. Просматривая экран пользователя, убедитесь, что всякий раз в программе упорядоченный набор данных
Упражнение 2. Исправить программу Sortirovka, для задачи 2.
Задача 2. Дан целочисленный массив. Отсортировать его по возрастанию
Тест: N = 10; элементы массива - 1, 2, 2, 2, -1, 1, 0, 34, 3, 3.
Ответ: -1, -1, 0, 1, 2, 2, 2, 3, 3, 34.
Упражнение 3. Исправить программу Sortirovka, добавив оценки по физике.
Домашнее задание.
Даны список футбольных команд и количество очков, набранных каждой командой. Вывести список команд по рейтингу. Дана температура за неделю, найти самый жаркий день и отсортировать по убыванию. Ответить на вопросы Что называется сортировкой? Какие методы сортировки вы знаете, опишите их отличия? Что вы понимаете под поиском? Почему при описании массивов предпочтительнее употреблять константы, а не указывать размеры в явном виде?«Информатика и информационные технологии»
читать $4.13.4 стр.218-220
1 Михаил Бараз, преподаватель « Основы программирования на языке Паскаль» электронный учебник. http://www. vzmakh. ru/info/pascal/modules/page14.html
