Методы сортировки план урока 10 класс

Обновлено: 01.07.2024

Урок для учащихся 10 класса с изучением информатики один час в неделю. Рассматриваются методы сортировки "пузырьковый и выбора, ознакомительно дается метод быстрой сортировки.

Вложение	Размер
plan_uroka_sortirovka_massiva_10_klass.docx	28.31 КБ
prilozhenie_1.pdf	315.29 КБ
sortirovka_massivov.pptx	262.33 КБ

Предварительный просмотр:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

for i:=1 to n-1 do

for j:=i+1 to n do

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

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

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

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

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

for i:=1 to n-1 do

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Предварительный просмотр:

Подписи к слайдам:

Сколько раз отработает цикл? Чему равно значение переменной A ? k:=4; a:=2; repeat a:=a+1; k := k -1; until k =0 ; a:=0; for i:=1 to 3 do for j:=1 to 2 do a := a +1;

Чему равно значение переменных a, b ? a :=5; b :=6; a := b ; b := a ; a=6 b=6 c :=a; a :=b; b :=c;

1 2 3 4 5 6 7 A : 12 9 -1 4 47 20 -10 Назовите размерность массива Назовите индексы нечетных элементов Найдите a[3]+a[7] Найдите максимальный элемент и его индекс

Сортировка массива – расстановка его элементов в заданном порядке Алгоритмы: простые и понятные, но неэффективные для больших массивов сложные, но эффективные по возрастанию, убыванию, последней цифре, сумме делителей, по алфавиту, …

Пузырьковый метод 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.

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;

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; k:=1; end; until k=0;

Метод пузырька с флажком 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 ; K:=1; end ; until k=0; < вывод массива >end.

Метод выбора Идея : найти минимальный элемент и поставить его на первое место. for i := 1 to N-1 do begin < найти номер nMin минимального элемента из A[i]..A[N] >if i <> nMin then begin < поменять местами A[i] и A[ nMin ] >end end;

Быстрая сортировка 14 78 6 82 67 55 44 34 L R 34 6 82 67 55 44 78 L R 34 6 44 67 55 82 78 L R 34 6 44 55 67 82 78 R L L > R : разделение закончено! !

Сравнение методов по времени N Метод пузырька Метод выбора Быстрая сортировка 1000 0,24 с 0,12 с 0,004 с 5000 5,3 с 2,9 с 0,024 с 15000 45 с 34 с 0,068 с

Домашнее задание Прочитать п.64 учебника Составить трассировочную таблицу пузырькового метода для 7 элементов Составить трассировочную таблицу метода пузырька с флажком для 7 элементов Составить программу сортировки методом выбора Задания 2-4 по выбору

По теме: методические разработки, презентации и конспекты

Разработки уроков потеме: "Числовая последовательность"

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

Учебно-методическая разработка по теме "Числовые последовательности"

Учебно-методическая разработка по теме "Числовые последовательности". Подбор заданий для закрепления материала в форме устного счёта вначале урока.

Сортировка строкового массива на Delphi

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

Разработка урока: Сортировка и фильтрация данных в электронной таблице. Условное форматирование.

Тема: Сортировка и фильтрация данных в электронной таблице. Условное форматирование.Цели урока:- рассмотреть назначение и использование сортировки и фильтрации данных в электронных таблицах, возможнос.

Презентация к уроку (8 класс) по теме "Массивы данных. Числовые массивы".

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

Методическая разработка для 8 класса по теме "Массивы данных. Числовые массивы". Раздел "Алгоритмизация и программирование".

Работа содержит основные сведения по теме "Массивы" в языке программирования Паскаль, конспекты уроков для 8 класса, примеры тестов, варианты контрольных работ для организации текущего и тем.

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

Для учителей информатики. Рассмотрены методы сортировки одномерных массивов, подобраны задания для закрепления материала.

Свидетельство и скидка на обучение каждому участнику

Зарегистрироваться 15–17 марта 2022 г.

Муниципальное автономное общеобразовательное учреждение

средняя общеобразовательная школа № 8 г. Белебея

муниципального района Белебеевский район

Республики Башкортостан

Урок информатики в 10 классе

СОРТИРОВКА МАССИВА МЕТОДОМ ОБМЕНА

Тагнер Анастасия Леонидовна,

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

высшая квалификационная категория

Урок информатики в 10 классе

Тема: СОРТИРОВКА МАССИВА МЕТОДОМ ОБМЕНА

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

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

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

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

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

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

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

Рассмотреть подробно сортировку массива методом прямого выбора.

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

Оборудование :

ПК, интерактивная доска, проектор, программное обеспечение – Windows 7, School Pascal .

Дидактическое обеспечение урока:

видеоматериалы ( Ролик 1, Ролик 2, Сортировка методом обмена , задание для самостоятельной работы (Приложение 1), алгоритм сортировки (Приложение 2), листинг основной программы (Приложение 3).

Основные понятия:

алгоритм сортировки методом обмена;

Предполагаемый результат урока:

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

Продукт урока:

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

Актуализация опорных знаний

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

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

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

Этапы урока

Деятельность учителя

Деятельность учащихся

Организационный момент

Приветствие обучающихся. Проверка готовности к уроку.

Здравствуйте, ребята! Я рада видеть вас на уроке информатики!

Актуализация опорных знаний

И начнем мы урок с просмотра видеоролика.

Вы, наверное, удивлены, каким образом связаны фигурное катание и информатика? Посмотрите внимательно на данный кадр? Что напоминают вам оценки судей за каждое выступление?

Числовой массив, состоящий из 5 элементов.

Дайте определение массива.

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

Какую задачу решил программист, обработав полученные оценки?

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

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

Поиск в массиве

Проверим ваши знания, выполнив самостоятельную работу.

Обучающиеся выполняют на местах проверочную работу по карточкам (см. Приложение 1)

Знания какого школьного предмета помогли вам без особых усилий выполнить 7-е задание?

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

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

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

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

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

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

Например, сортировка файла, содержащего фамилии, в алфавитном порядке.

-Как можно отсортировать массив?

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

Обучающиеся записывают определение в тетрадь.

По возрастанию или убыванию.

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

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

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

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

Учащиеся знакомятся с алгоритмом сортировки (см. Приложение 2)

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

- Для экономии времени возьмем заготовку основной программы из материалов прошлого урока.

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

Описание разработки

Цели урока:

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

Развивающая: развитие познавательного интереса учащихся

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

Тип урока: урок ознакомления с новым материалом

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

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

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

программное обеспечение – презентация по теме “Методы сортировки массивов”, Windows XP(Linux), АВС - Pascal(Free - Pascal).

Используемые технологии: компьютерные технологии обучения, технология личностно - ориентированного обучения

Ход урока:

Давайте повторим материал, пройденный ранее. (смотрите документ)

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

Сравните приведенные варианты программ с точки зрения эффективности.

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

Метод прямого выбора.

Алгоритм сортировки массива по возрастанию методом прямого выбора может быть представлен так:

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

Учитель демонстрирует алгоритм при помощи ИД.

Давайте попробуем записать этот алгоритм на Паскале.

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

Метод пузырька.

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

Учитель демонстрирует алгоритм при помощи ИД

Весь материал - смотрите архив.

-75%

Тема сортировки массивов очень важна в курсе алгоритмизации и программирования. Данная разработка урока значительно повышает интерес к изучению данной темы за счет авторской разработки тренажера для сортировки массивов. На уроке подробно рассмотрены самые популярные из всех известных сортировокметод "Пузырька", "Выбором","Вставками" и "Подсчетом"

МЕТОДИЧЕСКАЯ РАЗРАБОТКА УРОКА

«СОРТИРОВКА МАССИВОВ

ШУНТОВА ЛЮДМИЛА ВЛАДИМИРОВНА

МОУ Лесногородской сош

Одинцовского района Московской области

Существует традиционное деление алгоритмов на численные и нечисленные .

НЕЧИСЛЕННЫЕ

ЧИСЛЕННЫЕ АЛГОРИТМЫ

Математические расчеты

(вычисления по формулам,

решение уравнений,

статистическая обработка и т.д.

ДАННЫЕ -ЧИСЛА

НЕЧИСЛЕННЫЕ АЛГОРИТМЫ

Системное программирование

(трансляторы, ОС),СС управления Б.Д.,

сетевое программное обеспечение и т.д.

ДАННЫЕ-символьная,графическая, мультимедийная информация

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

От эффективности их выполнения во многом зависит эффективность работы всей программы.

внутренней сортировки – во внутренней памяти внешней сортировки- сортировки файлов

(во внутренней памяти)

(сортировка файлов)

Речь пойдет только о внутренней сортировке

Как правило, сортируемые данные располагаются в массивах.

В простейшем случае – сортируются числовые массивы .

Сортировка- упорядочивание данных по некоторому признаку.

Сортировка -процесс размещения заданного множества объектов в определенном порядке (убывания или возрастания)

Сортировка - один из наиболее распространенных процессов современной обработки информации. Это распределение элементов множества по группам в соответствии с определенными правилами.

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

СОРТИРОВКА ПОДСЧЕТОМ

Место каждого элемента в отсортированном массиве зависит от количества элементов, меньших его.

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

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

Исходный массив

Упорядоченный массив

алг.Сортировка подсчетом

СОРТИРОВКА ВЫБОРОМ

Сначала в неупорядоченном массиве выбирается минимальный элемент.

Этот элемент исключается из дальнейшей обработки , а оставшаяся последовательность элементов принимается за исходную, и процесс повторяется до тех пор, пока все элементы не будут выбраны. Выбранный в исходном массиве минимальный элемент размещается на первом месте в новом массиве.

Однако если на втором просмотре исходного массива вновь найти минимальный элемент, то им окажется тот же самый элемент .

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

алг.Сортировка выбором

min := a[1] indmin := 1

Второй способ сортировки выбором

Рассмотренный вариант сортировки обладает двумя недостатками:

Требование дополнительного массива
Для нахождения минимального элемента и его индек-са на каждом проходе приходится просматривать все элементы массива

Указанные недостатки устраняются, если все изменения проводить в исходном массиве:

Найти минимальный элемент среди всех элементов массива и поменять его местами с первым элементом
Найти минимальный элемент среди второго, третьего и т.д. элементов массива и поменять его местами со вторым элементом и т.д.
… .

В данной разработке урока применяется именно этот способ

алг.Сортировка выбором

for i := 1 to Dreal - 1 do

begin Min1 := 999999;

for j := i to Dreal do

begin if Mass [j]

begin k := j; Min1 := Mass [j];

for rab := 1 to dreal do

begin sss := sss + intToStr(Mass[rab]) + ' ';

ListBox3.ItemIndex := ListBox3.Count - 1;

СОРТИРОВКА ОБМЕНОМ

Метод, при котором все соседние элементы массива попарно сравниваются друг с другом и меняются местами, если предшествующий элемент больше последующего.

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

Затем процесс повторяется , и свое место занимает второй по величине элемент. Так продолжается до тех пор, пока весь массив не будет упорядочен.

Если последовательность сортируемых чисел расположить вертикально (где первый элемент исходного массива –внизу)

и проследить за перемещением элементов, то можно увидеть, что б о льшие элементы ,

Одномерный массив – это фиксированное количество элементов одного и того же типа, объединенных одним именем, где каждый элемент имеет порядковый номер (индекс).

Задание 1. Проверяем выполнение программы на языке программ-мирования Pascal .