Добавить материал и получить бесплатное свидетельство о публикации в СМИ
Эл. №ФС77-60625 от 20.01.2015

Автоматическая выдача свидетельства о публикации в официальном СМИ сразу после добавления материала на сайт - Бесплатно

Добавить свой материал

За каждый опубликованный материал Вы получите бесплатное свидетельство о публикации от проекта «Инфоурок»

(Свидетельство о регистрации СМИ: Эл №ФС77-60625 от 20.01.2015)

Инфоурок / Информатика / Конспекты / Урок "Сортировка элементов одномерного массива"
ВНИМАНИЮ ВСЕХ УЧИТЕЛЕЙ: согласно Федеральному закону № 313-ФЗ все педагоги должны пройти обучение навыкам оказания первой помощи.

Дистанционный курс "Оказание первой помощи детям и взрослым" от проекта "Инфоурок" даёт Вам возможность привести свои знания в соответствие с требованиями закона и получить удостоверение о повышении квалификации установленного образца (180 часов). Начало обучения новой группы: 26 апреля.

Подать заявку на курс
  • Информатика

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

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

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

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. Подведение итогов, оценки, завершение урока.

Автор
Дата добавления 12.09.2015
Раздел Информатика
Подраздел Конспекты
Просмотров578
Номер материала ДA-040146
Получить свидетельство о публикации

"Инфоурок" приглашает всех педагогов и детей к участию в самой массовой интернет-олимпиаде «Весна 2017» с рекордно низкой оплатой за одного ученика - всего 45 рублей

В олимпиадах "Инфоурок" лучшие условия для учителей и учеников:

1. невероятно низкий размер орг.взноса — всего 58 рублей, из которых 13 рублей остаётся учителю на компенсацию расходов;
2. подходящие по сложности для большинства учеников задания;
3. призовой фонд 1.000.000 рублей для самых активных учителей;
4. официальные наградные документы для учителей бесплатно(от организатора - ООО "Инфоурок" - имеющего образовательную лицензию и свидетельство СМИ) - при участии от 10 учеников
5. бесплатный доступ ко всем видеоурокам проекта "Инфоурок";
6. легко подать заявку, не нужно отправлять ответы в бумажном виде;
7. родителям всех учеников - благодарственные письма от «Инфоурок».
и многое другое...

Подайте заявку сейчас - https://infourok.ru/konkurs


Выберите специальность, которую Вы хотите получить:

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

ПЕРЕЙТИ В КАТАЛОГ КУРСОВ


Идёт приём заявок на международный конкурс по математике "Весенний марафон" для учеников 1-11 классов и дошкольников

Уникальность конкурса в преимуществах для учителей и учеников:

1. Задания подходят для учеников с любым уровнем знаний;
2. Бесплатные наградные документы для учителей;
3. Невероятно низкий орг.взнос - всего 38 рублей;
4. Публикация рейтинга классов по итогам конкурса;
и многое другое...

Подайте заявку сейчас - https://urokimatematiki.ru

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

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