Сортировка массива: алгоритмы и программная реализация
Цели и задачи
- Цель урока по SMART: к концу урока научиться объяснять принцип сортировки массива по возрастанию, выполнять сортировку методом выбора на небольшом массиве и записывать алгоритм в виде последовательности действий или программы на изучаемом языке программирования.
- Познакомить учащихся с назначением сортировки и различиями между упорядоченным и неупорядоченным массивом.
- Сформировать умение пошагово выполнять сортировку методом выбора и фиксировать изменения элементов массива.
- Развивать алгоритмическое мышление, умение находить ошибку в алгоритме и проверять результат на примере формата заданий ОГЭ.
- Воспитывать аккуратность при работе с данными, ответственность за проверку результата и уверенность при решении алгоритмических задач.
Планируемые результаты
Личностные
- Осознают практическую значимость сортировки при обработке больших объёмов данных.
- Снижают тревожность перед заданиями ОГЭ за счёт освоения понятного пошагового алгоритма.
- Проявляют готовность проверять собственное решение и исправлять найденные ошибки.
- Понимают связь алгоритмических навыков с будущей учебной и профессиональной деятельностью в сфере информационных технологий.
Метапредметные
- Выделяют существенные действия в алгоритме сортировки и представляют их в виде последовательности шагов.
- Сравнивают исходный и отсортированный массивы, объясняют причину перестановки элементов.
- Работают с условием алгоритмической задачи, извлекают из него данные и критерий результата.
- Планируют решение, выполняют самопроверку по контрольному массиву и корректируют ошибочные действия.
Предметные
- Знать назначение сортировки массива и понятия «элемент массива», «индекс», «минимальный элемент», «обмен».
- Уметь выполнять сортировку массива по возрастанию методом выбора.
- Уметь составлять таблицу состояний массива после каждого шага алгоритма.
- Уметь распознавать ошибки в псевдокоде сортировки и определять результат работы алгоритма.
- Владеть навыком записи простого алгоритма сортировки на изучаемом языке программирования.
Универсальные учебные действия (УУД)
Личностные УУД
- Осознают смысл изучения сортировки как универсального способа организации данных.
- Формируют ответственное отношение к точности вычислений и проверке программного результата.
- Оценивают собственную готовность к решению алгоритмических заданий ОГЭ.
- Проявляют познавательный интерес к способам обработки информации.
Регулятивные УУД
- Формулируют цель работы и планируют последовательность действий при сортировке массива.
- Удерживают алгоритм в рабочей памяти и фиксируют промежуточные состояния массива.
- Осуществляют пошаговый контроль и сверяют результат с условием задачи.
- Находят причину ошибки, вносят исправления и оценивают качество решения.
Познавательные УУД
- Анализируют структуру массива и определяют позицию минимального элемента.
- Сравнивают элементы, классифицируют массивы по степени упорядоченности.
- Строят информационную модель алгоритма в виде таблицы или псевдокода.
- Извлекают информацию из фрагмента программы и прогнозируют результат её выполнения.
Коммуникативные УУД
- Обсуждают в парах ход алгоритма, используя точные термины.
- Формулируют вопросы по непонятным шагам и аргументируют выбранный ответ.
- Сверяют решения с партнёром по заданным критериям.
- Корректно сообщают об ошибке и предлагают способ её исправления.
Подготовка учителя к уроку
- Подготовить презентацию или экранную таблицу с массивом [7, 3, 9, 2, 5] и его последовательным упорядочиванием по возрастанию.
- Подготовить карточки трёх уровней: базовые задания на выполнение сортировки, задания на анализ псевдокода и повышенное задание на исправление программы.
- Распечатать карточки базового уровня по одной на каждого ученика, всего 25 экземпляров; карточки повышенного уровня — по одной на парту.
- Подготовить лист самопроверки с эталонами массивов [4, 1, 6, 2] и [8, 3, 5, 1, 4].
- Вывести на доску памятку: «Найди минимум — поставь на текущую позицию — повтори для оставшейся части».
- Подготовить ноутбук учителя, проектор или интерактивную доску; при наличии компьютеров — среду программирования для демонстрации короткой программы.
- Разделить доску на зоны «Исходный массив», «Шаг алгоритма», «Результат», чтобы фиксировать ход рассуждений.
- Подготовить цветные маркеры или магниты для выделения текущей позиции и минимального элемента.
- Подготовить стикеры трёх цветов для приёма «Светофор» и билета на выход.
- Заранее записать на отдельном листе контрольный вопрос ОГЭ: определить результат выполнения фрагмента алгоритма сортировки.
Ход урока
Этап 1. Организационный момент и мотивация (3 мин)
Цель этапа: включить учащихся в учебную деятельность и показать практическую значимость сортировки.
Время | Действие учителя | Действие учеников |
|---|---|---|
1 мин | Учитель приветствует класс: "Здравствуйте, ребята. Проверьте, пожалуйста, готовность: тетрадь, ручка, карточка для работы. Сегодня мы будем не просто изучать новый алгоритм, а разберём способ, который используется при обработке списков товаров, результатов соревнований и данных в программах." | Проверяют готовность, записывают дату, настраиваются на работу. |
2 мин | Учитель показывает на экране неупорядоченный список результатов: 72, 15, 48, 91, 36. "Представьте, что это результаты участников соревнования. Как быстро получить список от меньшего результата к большему? Что должен сделать компьютер, если чисел не пять, а пять тысяч? Сегодня мы выясним, как программа сортирует массив и как подобные идеи встречаются в заданиях ОГЭ." | Предполагают: "Нужно сравнивать числа и менять их местами", "Нужно найти минимальное число и поставить первым". Формулируют предположение о теме урока. |
Завершение этапа: учитель подводит итог: "Мы увидели, что хаотичный набор данных трудно анализировать. Сегодня научимся превращать его в упорядоченный массив и проверим, как это связано с алгоритмическими заданиями ОГЭ."
Этап 2. Актуализация знаний (5 мин)
Цель этапа: восстановить знания о массивах, индексах, сравнении и обмене значений.
Время | Действие учителя | Действие учеников |
|---|---|---|
2 мин | Учитель проводит приём «Подумай — обсуди в паре — поделись»: "Запишите, что такое массив и с какого элемента обычно начинается его нумерация в используемом языке. Затем сравните ответ с соседом." | Индивидуально записывают определение, обсуждают в парах и формулируют: "Массив — набор однотипных элементов; индекс зависит от языка, часто отсчёт начинается с нуля или единицы". |
3 мин | Учитель записывает массив A = [7, 3, 9, 2, 5] и спрашивает: "Какой элемент находится на первой позиции? Как сравнить 7 и 3? Что означает обмен значений? Почему нельзя просто записать новое значение поверх старого?" Учитель демонстрирует обмен с использованием временной переменной. | Называют первый элемент 7, сравнивают 7 > 3, объясняют обмен: "Сначала сохраняем одно значение, затем присваиваем, иначе исходное значение потеряется". Записывают схему обмена: `temp = a; a = b; b = temp`. |
Завершение этапа: учитель подводит итог: "Мы вспомнили, что массив состоит из элементов с индексами, а обмен требует временного хранения значения. Теперь выясним, как повторять эти действия в правильном порядке."
Этап 3. Постановка проблемы и целеполагание (4 мин)
Цель этапа: выявить затруднение и совместно сформулировать цель урока.
Время | Действие учителя | Действие учеников |
|---|---|---|
2 мин | Учитель предлагает задачу: "Дан массив [7, 3, 9, 2, 5]. Нужно расположить элементы по возрастанию. Можно ли для этого один раз поменять местами 7 и 2 и считать задачу решённой?" Затем задаёт вопрос: "Что делать после первой перестановки?" | Отвечают: "Нет, после одной перестановки останутся неупорядоченные элементы". Называют необходимость повторять поиск и обмен. |
2 мин | Учитель фиксирует на доске ответы и спрашивает: "Какую цель поставим? Какие действия должен уметь выполнять каждый из вас к концу урока?" Учитель помогает уточнить измеримую формулировку. | Формулируют цель: "Научиться сортировать массив по возрастанию методом выбора, записывать шаги алгоритма и определять результат его работы". Записывают тему урока. |
Посмотрите план целиком
Зарегистрируйтесь — и откройте план урока по этой теме полностью: цели, ход урока и рефлексия по ФГОС.
Завершение этапа: учитель подводит итог: "Затруднение найдено: отдельные перестановки не дают готового результата. Нам нужен повторяемый алгоритм с понятным условием остановки. Сейчас построим его вместе."
Этап 4. Открытие нового знания: сортировка методом выбора (10 мин)
Цель этапа: открыть и осмыслить алгоритм сортировки методом выбора на конкретном массиве.
Время | Действие учителя | Действие учеников |
|---|---|---|
4 мин | Учитель показывает массив [7, 3, 9, 2, 5] и выделяет его первую позицию: "На первом шаге просмотрим весь массив и найдём минимальный элемент. Минимум равен 2. Теперь поменяем местами 7 и 2. Получаем [2, 3, 9, 7, 5]. Первая позиция готова. Мы не трогаем её и переходим к оставшейся части." | Следят за выделением элементов, называют минимум 2, фиксируют первый обмен и состояние массива после шага. |
3 мин | Учитель продолжает: "Во второй части [3, 9, 7, 5] минимальный элемент равен 3, он уже находится на нужной позиции. На третьем шаге рассматриваем [9, 7, 5], выбираем 5 и меняем его с 9. Получаем [2, 3, 5, 7, 9]." На доске учитель отмечает готовую часть массива. | Определяют минимумы в оставшихся частях, проговаривают: "Минимум уже стоит на месте" или "Нужно поменять 9 и 5". Заполняют таблицу шагов. |
3 мин | Учитель формулирует алгоритм: "Первое: считаем текущую позицию. Второе: ищем минимальный элемент справа от неё. Третье: меняем его с элементом текущей позиции. Четвёртое: сдвигаем текущую позицию вправо. Повторяем, пока не обработана вся последовательность. Такой способ называется сортировкой методом выбора." | Записывают четыре шага алгоритма, задают уточняющие вопросы, объясняют соседу принцип метода своими словами. |
Запись в тетрадях
Сортировка — упорядочивание элементов массива по выбранному правилу. Метод выбора: на каждой позиции найти минимальный элемент в неотсортированной части массива и обменять его с первым элементом этой части. Для сортировки по убыванию вместо минимума выбирают максимум.
Завершение этапа: учитель подводит итог: "Мы получили алгоритм, в котором на каждом шаге готовится одна позиция. Главное правило — искать минимум только в ещё не отсортированной части. Теперь проверим алгоритм вместе, не пропуская ни одного сравнения."
Этап 5. Первичное закрепление. Таблица состояний (7 мин)
Цель этапа: закрепить выполнение сортировки вручную и научиться фиксировать промежуточные результаты.
Время | Действие учителя | Действие учеников |
|---|---|---|
2 мин | Учитель раздаёт карточки с массивом [8, 4, 6, 1, 3]: "Работаем в парах. В таблице есть строки для шагов. В каждой строке укажите не только новый массив, но и элемент, который был выбран минимумом. На выполнение — две минуты." | В парах находят минимальный элемент, записывают первый обмен и подписывают выбранный минимум. |
3 мин | Учитель организует проверку приёмом «Снежный ком»: "Сначала сравните первый шаг в паре, затем объединитесь с соседней парой и сверяйте всю последовательность. Если ответы расходятся, найдите первое различие." | Сверяют последовательность в малых группах, находят расхождение, аргументируют, почему минимум выбран правильно. |
2 мин | Учитель выводит эталон на экран: [1, 4, 6, 8, 3] → [1, 3, 6, 8, 4] → [1, 3, 4, 8, 6] → [1, 3, 4, 6, 8]. "Поднимите зелёную карточку, если получили такой результат; жёлтую — если была одна неточность; красную — если нужен разбор." | Сверяют свои записи, поднимают карточки, исправляют ошибки и формулируют причину неточности. |
Эталон решения
Исходный массив: [8, 4, 6, 1, 3]. Шаг 1: минимум всего массива — 1; обмен 8 и 1: [1, 4, 6, 8, 3]. Шаг 2: минимум части [4, 6, 8, 3] — 3; обмен 4 и 3: [1, 3, 6, 8, 4]. Шаг 3: минимум части [6, 8, 4] — 4; обмен 6 и 4: [1, 3, 4, 8, 6]. Шаг 4: минимум части [8, 6] — 6; обмен: [1, 3, 4, 6, 8].
Завершение этапа: учитель подводит итог: "Мы научились выполнять сортировку не наугад, а по таблице состояний. Теперь каждый попробует определить результат алгоритма самостоятельно, как это требуется в заданиях на анализ программы."
Этап 6. Самостоятельная работа с самопроверкой (9 мин)
Цель этапа: проверить индивидуальное понимание алгоритма и потренировать задания, близкие к формату ОГЭ.
Время | Действие учителя | Действие учеников |
|---|---|---|
5 мин | Учитель раздаёт индивидуальные карточки: "Выполните сортировку массива [6, 2, 9, 4, 1] методом выбора. Запишите минимум на каждом шаге и итоговый массив. Затем определите, какой массив получится после двух шагов." Учитель напоминает: "Не пропускайте промежуточные записи." | Индивидуально выполняют сортировку: [1, 2, 9, 4, 6] после первого шага; [1, 2, 9, 4, 6] после второго шага; продолжают до результата [1, 2, 4, 6, 9]. |
2 мин | Учитель показывает эталон и предлагает самопроверку: "Поставьте плюс за правильный выбор минимума, плюс за каждую верную перестановку и отдельно проверьте итоговый порядок." | Сверяют работу с эталоном, отмечают ошибки, исправляют их другим цветом. |
2 мин | Учитель предлагает задание повышенного уровня: "В алгоритме вместо поиска минимума в оставшейся части каждый раз ищут минимум во всём массиве. Объясните, почему такой вариант может нарушить результат." | Формулируют ответ: "Уже отсортированные элементы могут снова поменяться местами, поэтому текущая позиция и граница обработанной части обязательны". |
Завершение этапа: учитель подводит итог: "Индивидуальная проверка показала, что результат зависит от строгого соблюдения границы неотсортированной части. Осталось связать ручное выполнение с записью алгоритма и подвести итог урока."
Этап 7. Применение и запись алгоритма (4 мин)
Цель этапа: представить сортировку в форме псевдокода и установить связь с программированием.
Время | Действие учителя | Действие учеников |
|---|---|---|
2 мин | Учитель выводит псевдокод: "Для каждой позиции i найти индекс минимального элемента в части массива от i до конца; обменять элементы на позициях i и minIndex. Посмотрите, какие слова повторяются и за что они отвечают." | Выделяют повторение цикла, поиск минимума и обмен; объясняют назначение переменных i и minIndex. |
2 мин | Учитель демонстрирует фрагмент программы на изучаемом языке и говорит: "Я не требую сегодня запомнить синтаксис целиком. Важно увидеть соответствие: внешний цикл задаёт позицию, внутренний ищет минимум, обмен меняет элементы. Именно такое понимание помогает решать задания на определение результата программы." | Соотносят строки программы с шагами алгоритма, называют строку поиска минимума и строку обмена. |
Завершение этапа: учитель подводит итог: "Алгоритм, таблица и программа описывают один и тот же процесс разными способами. Сейчас зафиксируем, что каждый из вас понял и что ещё требует тренировки."
Этап 8. Рефлексия, оценивание и домашнее задание (3 мин)
Цель этапа: оценить достижение цели урока, выявить затруднения и дать посильное продолжение работы.
Время | Действие учителя | Действие учеников |
|---|---|---|
1 мин | Учитель проводит приём «Билет на выход»: "На стикере завершите две фразы: «Сортировка методом выбора начинается с…» и «Моя типичная ошибка при выполнении алгоритма…»." | Пишут ответы: "с поиска минимума в неотсортированной части"; называют собственную трудность, например пропуск шага или неверный обмен. |
1 мин | Учитель обращается к классу: "Поднимите зелёный стикер, если можете самостоятельно отсортировать массив из пяти элементов; жёлтый, если нужна ещё одна тренировка; красный, если алгоритм пока неясен." | Выбирают цвет, соотносят его с личной готовностью. |
1 мин | Учитель сообщает домашнее задание и критерии: "Выберите обязательный уровень, а при уверенности добавьте повышающий или дополнительный. Номера заданий не нужны: работаем по описанию." | Записывают выбранный уровень и контрольные вопросы. |
Завершение этапа: учитель подводит итог: "Сегодня вы научились упорядочивать массив методом выбора, фиксировать каждый шаг и читать алгоритм как основу программы. Ошибка в одном сравнении меняет дальнейший результат, поэтому проверка так же важна, как и сам алгоритм."
Критерии оценивания практической работы
- «5» — полностью и без ошибок выполнена сортировка массива из пяти элементов, верно записаны все промежуточные состояния, объяснён принцип метода выбора и правильно определён результат алгоритма.
- «4» — выполнена сортировка и получен правильный итоговый массив, но допущена одна ошибка в промежуточной записи или недостаточно полно объяснён один шаг.
- «3» — правильно определён итоговый порядок элементов или выполнены не менее двух шагов сортировки, но допущены ошибки в выборе минимума, обмене либо фиксации последовательности.
- «2» — алгоритм не применён, итоговый массив не получен или записи не позволяют восстановить ход решения.
Рефлексия
Вопрос для ученика | Цель вопроса |
|---|---|
Что делает алгоритм сортировки на каждом шаге? | Проверка понимания основной идеи метода выбора. |
Почему минимум ищется только в неотсортированной части массива? | Выявление понимания границы обработанных данных. |
На каком шаге вы могли ошибиться и как обнаружили ошибку? | Формирование навыка самоконтроля и коррекции. |
Насколько уверенно вы решите похожее задание ОГЭ самостоятельно? | Определение субъективной готовности и уровня тревожности. |
Завершающее слово учителя
"Сегодня мы разобрали сортировку массива методом выбора: на каждой позиции находили минимальный элемент оставшейся части и выполняли обмен. Важно не только получить красивый итоговый ряд, но и уметь объяснить каждый промежуточный шаг. Типичная ошибка — искать минимум во всём массиве и забывать о уже обработанной части. На следующем уроке мы сравним разные способы сортировки и обсудим, какой алгоритм удобнее в разных ситуациях. Не бойтесь заданий ОГЭ: если разбить программу на шаги и вести таблицу состояний, даже сложный фрагмент становится проверяемым."
Домашнее задание
Уровень | Что задать | Зачем |
|---|---|---|
Базовый (обязательный) | Выполнить сортировку методом выбора для трёх массивов по 5 элементов: два массива упорядочить по возрастанию и один — по убыванию. Для каждого массива записать промежуточные состояния. | Закрепляет алгоритм поиска минимума или максимума и последовательность обменов; при проверке смотреть на каждый шаг, а не только на итоговый массив. |
Средний (повышающий) | Решить 2 задания на определение результата работы фрагмента программы сортировки и одно задание на поиск ошибки в псевдокоде. Обязательно объяснить, на каком шаге возникает ошибка. | Формирует навык чтения алгоритма и подготовки к заданиям ОГЭ; при проверке оценивать аргументацию и точность отслеживания индексов. |
Продвинутый (дополнительный) | Составить собственный псевдокод сортировки массива из 6 элементов по возрастанию, привести пример работы и кратко сравнить метод выбора с последовательным обменом соседних элементов. | Развивает умение создавать алгоритм и сравнивать способы решения; при проверке смотреть на корректность циклов, условие выбора элемента и полноту примера. |
Контрольные вопросы перед выходом: «Что называется сортировкой массива? Какой элемент выбирается на первом шаге сортировки по возрастанию? Почему после фиксации минимального элемента поиск продолжается только справа от него? Какие три действия нужно проверить при анализе алгоритма: поиск, обмен и переход к следующей позиции?»
