Сортировка массивов
план-конспект урока по информатике и икт (11 класс) по теме
Предварительный просмотр:
Сортировка массивов.
Клименкова Альбина Евгеньевна
Цель:
- Рассмотрение актуальности сортировки массивов.
- Разбор на примерах разнообразия алгоритмов сортировки.
- Воспитание умения воспринимать достаточно сложные алгоритмические конструкции.
- Развитие творческого мыслительного потенциала.
Сортировка - это один из наиболее распространённых процессов современной обработки данных. Сортировкой называется распределение элементов множества по группам в соот ветствии с определёнными правилами. Например, сортировка элементов массива, в резуль тате которой получается массив, каждый элемент которого, начиная со второго, не боль ше стоящего от него слева, называется сортировкой по невозрастанию.
Задача. Сформировать целочисленный массив М из 20 элементов. Вывести на экран не сортированный массив М. Отсортировать массив по невозрастанию. Вывести отсортирован ный массив.
Решение. Запишем общий вид решения этой задачи, не детализируя пока метод сортировки:
Рассмотрим отдельно блок сортировки. Существует несколько методов сортировки. Рассмотрим три метода: линейную сортировку, сортировку методом пузырька и метод бы строй сортировки с разделением. В качестве примера применения каждого метода будем рассматривать одну и ту же задачу (см. ниже), чтобы иметь возможность объективно сравнить эффективность разных методов.
1. Линейная сортировка
а) Описание метода.
(Линейную сортировку в некоторой литературе называют также «сортировкой отбо ром».) Идея линейной сортировки по невозрастанию заключается в том, чтобы, последова тельно просматривая весь массив, отыскать наибольшее число и поместить его на первую позицию. Затем просматриваются все оставшиеся элементы массива и выполняется анало гичная операция по отбору из рассматриваемой части массива максимального элемента и обмену местами этого элемента и первого в рассматриваемой части и т. д.
Рассмотрим подробнее работу этого метода на примере. Пусть требуется упорядочить по невозрастанию массив А из 4 элементов:
2. Сортировка методом пузырька
а) Описание метода.
«Пузырьковый» метод основан на том, что в процессе исполнения алгоритма более «легкие» (наименьшие по значению) элементы массива постепенно «всплывают». Особенно стью данного метода является сравнение не каждого элемента со всеми, а сравнение в парах соседних элементов. Алгоритм пузырьковой сортировки по невозрастанию состоит в последовательных просмотрах снизу вверх (от начала к концу) массива М. Если соседние элементы таковы, что выполняется условие М[i] < М[i+1], то выполняется обмен значениями этих элементов.
Рассмотрим подробнее работу этого метода на примере. Пусть требуется упорядочить по невозрастанию массив А из 4 элементов (условные обозначения те же):
3. Метод быстрой сортировки с разделением (дополнительно, на усмотрение преподавате ля для хорошо успевающих учеников)
а) Описание метода.
Линейная и пузырьковая сортировки просты и наглядны, но не очень эффективны с точки зрения скорости работы алгоритма, т. к. для их реализации используются двойные циклы , т.е. независимо от вида массива каждая сортировка выполняется за одно и то же число шагов (свое для каждого метода) для массивов одинаковой длины. Значительно бы стрее работает алгоритм сортировки с разделением или «быстрой сортировки», т. к. этот метод не использует цикл с параметром. В основе алгоритма лежит метод последователь ного дробления массива на части. Количество шагов, которые выполняются при использо вании этого метода, определяется видом массива (из каких элементов он состоит) и не яв ляется фиксированным для массивов одинаковой длины, за счет чего достигается увели чение скорости выполнения сортировки.
б) Схема алгоритма (для задачи).
По теме: методические разработки, презентации и конспекты
![](/sites/default/files/pictures/2013/06/26/picture-270255-1372190548.jpg)
Одномерные массива. Сортировка методом прямого выбора.
Рассматривается данный алгоритм и обсуждается вопрос оценки сложности данного алгоритма....
Сортировка массива. Метод пузырька.
Презентация к учебнику "Информатика 10 класс" авторы Поляков К.Ю., Еремин Е.А. Глава 8 "Алгоритмизация и программирование", §64 "Сортировка".Демонстрация презентации дает наглядное представление выпол...
![](/sites/default/files/pictures/2016/11/03/picture-842710-1478191539.jpg)
Сортировки массивов.
Три сортировка массивов на языке программирования Паскаль, задачи на сортировки...
Сортировка массивов.
Описаны алгоритмы сортировки, приведены примеры подпрограмм на Паскале....
Сортировка массива
Презентация по теме: "Сортировка массивов". В презентации расссмотрены определение сортировки, краткая история развития, несколько способов сорттировки, в частности следующие алгоритмы1.Сортировка пуз...
![](/sites/default/files/pictures/2020/04/06/picture-386619-1586154221.jpg)
Дистанционный урок информатики в 9 классе по теме "Решение задач на сортировку массива"
Данная разработка может быть использована для проведения дистанционного урока информатики....