Инфоурок / Информатика / Конспекты / Урок "Сортировка элементов одномерного массива"
Обращаем Ваше внимание, что в соответствии с Федеральным законом N 273-ФЗ «Об образовании в Российской Федерации» в организациях, осуществляющих образовательную деятельность, организовывается обучение и воспитание обучающихся с ОВЗ как совместно с другими обучающимися, так и в отдельных классах или группах.

Педагогическая деятельность в соответствии с новым ФГОС требует от учителя наличия системы специальных знаний в области анатомии, физиологии, специальной психологии, дефектологии и социальной работы.

Только сейчас Вы можете пройти дистанционное обучение прямо на сайте "Инфоурок" со скидкой 40% по курсу повышения квалификации "Организация работы с обучающимися с ограниченными возможностями здоровья (ОВЗ)" (72 часа). По окончании курса Вы получите печатное удостоверение о повышении квалификации установленного образца (доставка удостоверения бесплатна).

Автор курса: Логинова Наталья Геннадьевна, кандидат педагогических наук, учитель высшей категории. Начало обучения новой группы: 27 сентября.

Подать заявку на этот курс    Смотреть список всех 216 курсов со скидкой 40%

Урок "Сортировка элементов одномерного массива"

библиотека
материалов

Сортировка элементов линейного массива различными способами.

1-й урок. Поиск способов сортировки.

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

Вид урока: урок объяснения нового материала.

Цели урока:

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

  1. закрепить полученные знания по теме «Линейный массив».

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

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

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

  2. формировать и развивать гибкость мышления.

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

  4. развивать умение применять полученные знания на практике.

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

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

Ход урока.

  1. Приветствие учащихся. Отмечаем отсутствующих.

  2. Объявление цели урока и плана работы на уроке.

  3. Вопросы на повторение теоретического и практического материала.

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

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

Теоретическая часть.

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

Все методы сортировки можно разделить на две большие группы:

    1. прямые методы сортировки; 2) улучшенные методы сортировки.

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

hello_html_5b970866.gif

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

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

      1. сортировка вставкой (включением);

      2. сортировка выбором (выделением);

      3. сортировка обменом ("пузырьковая").

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

Поиск способов сортировки. Рассмотрим некоторый «массив» и попробуем его отсортировать. На столе в хаотичном порядке ставятся матрешки. Как будем сортировать? (учащиеся предлагают свои способы сортировки), предложенным способам даются свои «названия», которые записываются.

Способ 1. Будем сравнивать элементы попарно, начиная с 1-го. В паре отыскивать наибольший элемент, и если он стоит левее в данной паре, то поменяем его местами с «соседом». После одного такого «пробега» на последней позиции массива будет стоять максимальный элемент. Поскольку максимальный элемент уже стоит на своей последней позиции, то второй пробег обменов выполняется до предпоследнего (N-1-го) элемента. И так далее. Такой метод называется сортировка обменом ("пузырьковая" сортировка). Применим метод к нашему «массиву». Снова сортируем «массив», меняя исходное расположение матрешек.

Рассмотрим общую схему метода сортировки «пузырьком».

Оhello_html_m73370901.pngтвечаем на вопросы:

Элемент с каким индексом последний раз в 1-м пробеге будет «сравниваться» со своим соседом справа? (с индексом N-1)

Сколько элементов встанет на свои место после окончания 1-го пробега сравнений, 2-го пробега, I-го пробега? (1,2,I)

Как выполнить перестановку местами элементов в паре? (надо ввести дополнительную переменную)

Сколько может понадобиться пробегов сравнений для того, чтобы массив стал упорядоченным? (минимум – 1, максимум - N-1)

От чего это зависит? (от исходного расположения элементов в массиве)

Как вы думаете, сколько циклических «пробегов» в самом «худшем» случае нужно, что упорядочить все элементы массива? (N-1).


Способ 2. Находим (выбираем) в массиве элемент с минимальным значением на интервале от 1-го элемента до N-го (последнего) элемента и меняем его местами с первым элементом. На втором шаге находим элемент с минимальным значением на интервале от 2-го до n-го элемента и меняем его местами со вторым элементом. И так далее для всех элементов. Такой способ называется сортировка «выбором».

Очевидно, что процесс будет повторяться N-1 раз, т.к. сравнивать последний элемент сам с собой не имеет смысла.

Рассматриваем схему сортировки «выбором» для общего случая.

Оhello_html_36555c6b.pngтвечаем на вопросы:

Что означает каждый этап (1-2-3)?

(1 этап – поиск минимального элемента, сохранение его значения и индекса)

Сколько элементов отсортировано в начале I –го шага? (I-1 элемент)

Сколько элементов будет отсортировано в конце I –го шага? (I элементов)

Как происходит поиск минимального элемента?

Как происходит перестановка элементов местами? (через переменную MIN)



К 3-му способу учащиеся приходят не сразу, им нужна подсказка.

Способ 3. Сортировка «вставкой».

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

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

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

И так далее. Процесс будет повторяться циклически N-1 раз (N – размерность массива).

Рассмотрим схему метода.

Массив также делится на две части: отсортированную (левую) и неотсортированную (правую).

В начале работы алгоритма в качестве неотсортированной части берут все элементы массива.

Оhello_html_m4664d53.pngтвечаем на вопросы:

Сколько элементов будет отсортировано в начале I шага? (ответ: I-1)

Как будет происходить сдвиг элементов?

Сколько элементов будет отсортировано после окончания I-го шага? (ответ: I)

Как вы думаете, сколько раз повторится данный алгоритм? (ответ: N-1 раз, т.к. в конце N-1 шага на месте окажется N-1 элемент, а последний автоматически займет нужную позицию).

Таким образом, алгоритм будет состоять из п-1-го шага ( п - размерность массива), каждый из которых будет включать следующие действия (для сортировки по возрастанию)

  1. поиск минимального элемента и сохранение найденного элемента и его индекса;

  2. сдвиг элементов, стоящих в неотсортированной части массива левее минимального, вправо;

  3. вставка найденного минимального элемента в «свободную» после сдвига ячейку.


  1. Подведение итогов.

Что вы узнали о сортировках массива? Какие способы нашли? В чем заключается смысл каждого способа? Какой способ, по вашему мнению, наиболее длинный? Самый быстрый (короткий)?

  1. Выставление оценок учащимся. Завершение урока.

2-й урок. Составление программ для сортировки массива.

Тип урока: практическое занятие.

Вид урока: закрепление изученного материала

Цели урока:

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

  1. самостоятельно разработать программу, произвести ее отладку и тестирование;

  2. закрепить навыки работы в среде TurboPascal;

  3. научить использовать полученные ранее теоретические сведения на практике;

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

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

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

  3. формировать и развивать гибкость мышления, интуицию;

  4. развивать память, внимание.

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

Пособия и наглядные материалы. ПК, плакаты, карточки с заданиями.

Ход урока.

  1. Начало урока.

  2. Объявление цели урока и плана работы на уроке.

  3. Повторение пройденного материала.

Перед началом урока учащиеся разбиваются на группы (по 2-3 человека) и каждая группа в начале урока получает задание: составить программу для конкретного способа сортировки. Каждая группа получает карточку со схемой заданного способа сортировки и карточку с вопросами.

Какие способы сортировки мы нашли? В чем заключается суть каждого метода. По общей схеме каждого метода сортировки находим ответы на вопросы:

    1. Сколько операторов цикла надо использовать.

    2. Для чего используется внешний цикл и как изменяется значение его параметра.

    3. Нужно ли выполнить какие-то подготовительные действия в теле внешнего цикла перед началом работы оператора внутреннего цикла.

    4. Для чего используется внутренний цикл и как изменяется значение его параметра.

    5. Какие операторы будут использоваться и для чего в теле внутреннего цикла.

    6. Будут ли выполняться какие-либо действия после завершения работы внутреннего цикла и до возврата к внешнему циклу в каждом из рассмотренных способов.

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

      • Как найти максимальный (минимальный) элемент в массиве?

      • Как осуществить перестановку элементов местами (например, поменять местами I-й и J -й элементы массива)

      • Как осуществить сдвиг (смещение) элементов на 1 позицию вправо?

      • Как осуществить сдвиг (смещение) элементов на 1 позицию влево?

В ходе размышлений приходим к таким ответам:

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

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

Для сортировки методом «выбора» используется 2 цикла. Оператор «внешнего цикла» – увеличивает длину левой (отсортированной) части массива, т.е. параметр цикла (I) изменяется от 1 до N-1.

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

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

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

Для сортировки методом «вставки» используется 2 цикла. Работа и назначение их аналогично методу «выбора», но после завершения работы внутреннего цикла происходит:

А) сдвиг элементов, стоящих в неотсортированной части массива левее минимального, вправо;

Б) вставка найденного минимального элемента в «свободную» после сдвига ячейку.

Напоминание ученикам:

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


  1. Практическая часть (составление программы сортировки массива).

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

  1. Подведение итогов, оценки, завершение урока.



Самые низкие цены на курсы переподготовки

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

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

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

Начало обучения ближайшей группы: 27 сентября. Оплата возможна в беспроцентную рассрочку (10% в начале обучения и 90% в конце обучения)!

Подайте заявку на интересующий Вас курс сейчас: https://infourok.ru

Общая информация

Номер материала: ДA-040146

Похожие материалы

2017 год объявлен годом экологии и особо охраняемых природных территорий в Российской Федерации. Министерство образования и науки рекомендует в 2017/2018 учебном году включать в программы воспитания и социализации образовательные события, приуроченные к году экологии.

Учителям 1-11 классов и воспитателям дошкольных ОУ вместе с ребятами рекомендуем принять участие в международном конкурсе «Законы экологии», приуроченном к году экологии. Участники конкурса проверят свои знания правил поведения на природе, узнают интересные факты о животных и растениях, занесённых в Красную книгу России. Все ученики будут награждены красочными наградными материалами, а учителя получат бесплатные свидетельства о подготовке участников и призёров международного конкурса.

Конкурс "Законы экологии"