Конспект для ученика по теме «Сортировка»

20
2

Конспект по теме «Сортировка» с подробным объяснением темы будет полезен для 11-классников. Материал актуален для подготовки к ЕГЭ.

Цель:

  1. Рассмотрение актуальности сортировки массивов.
  2. Разбор на примерах разнообразия алгоритмов сортировки.
  3. Воспитание умения воспринимать достаточно сложные алгоритмические конструкции.
  4. Развитие творческого мыслительного потенциала.

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

Задача. Сформировать целочисленный массив М из 20 элементов. Вывести на экран не­сортированный массив М. Отсортировать массив по невозрастанию. Вывести отсортирован­ный массив.

Решение. Запишем общий вид решения этой задачи, не детализируя пока метод сортировки:

89

Рассмотрим отдельно блок сортировки. Существует несколько методов сортировки. Рассмотрим три метода: линейную сортировку, сортировку методом пузырька и метод бы­строй сортировки с разделением. В качестве примера применения каждого метода будем рассматривать одну и ту же задачу (см. ниже), чтобы иметь возможность объективно сравнить эффективность разных методов.

  1. Линейная сортировка

а) Описание метода.

(Линейную сортировку в некоторой литературе называют также «сортировкой отбо­ром».) Идея линейной сортировки по невозрастанию заключается в том, чтобы, последова­тельно просматривая весь массив, отыскать наибольшее число и поместить его на первую позицию. Затем просматриваются все оставшиеся элементы массива и выполняется анало­гичная операция по отбору из рассматриваемой части массива максимального элемента и обмену местами этого элемента и первого в рассматриваемой части и т. д.

Рассмотрим подробнее работу этого метода на примере. Пусть требуется упорядочить по невозрастанию массив А из 4 элементов:

84

85

86

  1. Сортировка методом пузырька

а) Описание метода.

«Пузырьковый» метод основан на том, что в процессе исполнения алгоритма более «легкие» (наименьшие по значению) элементы массива постепенно «всплывают». Особенно­стью данного метода является сравнение не каждого элемента со всеми, а сравнение в парах соседних элементов. Алгоритм пузырьковой сортировки по невозрастанию состоит в последовательных просмотрах снизу вверх (от начала к концу) массива М. Если соседние элементы таковы, что   выполняется условие М[i] < М[i+1], то выполняется обмен значениями этих элементов.

Рассмотрим  подробнее работу этого метода на примере. Пусть требуется упорядочить по невозрастанию массив А из 4 элементов (условные обозначения те же):

87

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

а) Описание метода.

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

б) Схема алгоритма (для задачи).

20
2
Текст прошел проверку у экспертов «ИнПро» ®
педагог по информатике
педагог по информатике
педагог по информатике
Ирина Михайловна
методист образовательного холдинга «ИнПро»

Справочно:

Материалы подготовлены Федеральным образовательным сервисом «ИнПро»® – Лицензия Минобрнауки 22Л01 № 0002491.

Готовим детей к школе, а также подтягиваем по школьной программе по всей России в 40+ центрах и онлайн, в том числе в Вашем городе.

Бесплатная горячая линия: 8 800 250 62 49 (с 6 до 14 по Мск).


Следите за новостями в социальных сетях:


Нужен репетитор? Запишитесь на бесплатное пробное занятие в «ИнПро»®

Отправка запроса ни к чему не обязывает, это бесплатно. Будем рады помочь!

Отправляя заявку, Вы соглашаетесь на обработку персональных данных.


В текущем разделе «1.19 Сортировка » также читают

Нужен репетитор?
Запишитесь на бесплатное пробное занятие в «ИнПро»®

Отправка запроса ни к чему не обязывает, это бесплатно. Будем рады помочь!

Отправляя заявку, Вы соглашаетесь на обработку персональных данных.
Записаться на бесплатное занятие Бесплатное занятие