Прием в авторские монографии до 20 марта 2016 г.

Е.В. Рогачева, А.А. Новиков
Самарский государственный университет
ПРИМЕНЕНИЕ ПРОСТЫХ МЕТОДОВ СОРТИРОВКИ
К РАЗЛИЧНЫМ СТРУКТУРАМ ДАННЫХ
Предлагается при изучении простых методов сортировки рассмотреть технические аспекты сортировки различных структур данных, а также провести сравнительный анализ эффективности этих методов на примере массива, файла и двунаправленного списка с элементами, содержащими не только ключ (по которому выполняется сортировка), но и информационную часть. Приводится фрагмент сравнительного анализа.
При изучении методов сортировки обычно ограничиваются их рассмотрением на примере массивов. Использование статического целочисленного массива в качестве модельной структуры данных (например, [1]), несомненно, оправданно, поскольку позволяет сосредоточиться именно на сути алгоритма, а не на конкретных деталях его реализации. Вместе с тем последующее изучение технических аспектов представляется также весьма полезным, поскольку позволяет продемонстрировать важность анализа временной сложности не только алгоритма, но и его реализации с учетом структуры данных. Проведение такого анализа на примерах простых методов сортировки не требует от обучающегося серьезной математической подготовки. Вместе с тем, поскольку основу многих усовершенствованных методов сортировки составляют идеи, развитые в рамках простых методов, анализ последних заметно облегчает выполнение приблизительной оценки сложности первых (точная оценка является весьма нетривиальной и сложной задачей, см., например, [2]).
Здесь мы ограничимся рассмотрением трех простых методов сортировки – выбором, вставкой, обменом. Методы сортировки оценивают по двум параметрам – количеству сравнений и количеству перемещений элементов, и оценки для простых методов приводятся в ряде источников (например, [2], [3]). Однако самостоятельное выполнение обучающимися анализа разработанных ими программ и сравнение полученных результатов с теоретической оценкой представляется целесообразным, поскольку обращает их внимание на различные характеристики входных данных (строение, исходную упорядоченность и т.п.). Такой анализ несложен, и в случае использования в качестве сортируемого набора данных массива требует введения в процедуру сортировки двух дополнительных целочисленных параметров (или локальных переменных, в зависимости от реализации), которые изменяются при выполнении сравнения или перемещения элемента соответственно.

Полный вариант статьи вы можете заказать за 50 руб.
Варианты оплаты



Rambler's Top100