ИТО-Марий Эл-2008 / Развитие региональной информационной образовательной среды : только публикация 

ВОЗМОЖНОСТИ ИСПОЛЬЗОВАНИЯ ГРАФИЧЕСКОЙ ИНТЕРПРЕТАЦИИ МЕТОДОВ СОРТИРОВКИ ДЛЯ ПРЕПОДАВАНИЯ ЯЗЫКОВ ПРОГРАММИРОВАНИЯ ВЫСОКОГО УРОВНЯ

Сергеенко Сергей Владимирович

Смоленский филиал Российского государственного открытого технического университета путей сообщения

задать вопрос автору

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

В общей постановке задача сортировки данных формируется следующим образом. Имеется последовательность однотипных записей, одно из полей которых выбрано в качестве ключевого (ключ сортировки). Тип данных ключа должен включать операции сравнения. Задачей сортировки является преобразование исходной последовательности в последовательность, содержащую те же записи, но в порядке возрастания (или убывания) значений ключа.

Различают сортировку массивов записей, целиком расположенных в основной памяти (внутреннюю сортировку), и сортировку файлов, хранящихся во внешней памяти и не помещающихся полностью в основной памяти (внешнюю сортировку). Для внутренней и внешней сортировки требуются существенно разные методы. В лекциях рассматриваются наиболее известные методы внутренней сортировки, начиная с простых и понятных, но не слишком быстрых, и заканчивая не столь просто понимаемыми усложненными методами.

Естественным условием, предъявляемым к любому методу внутренней сортировки, является то, что эти методы не должны требовать дополнительной памяти: все перестановки с целью упорядочения элементов массива должны производиться в пределах того же массива. Мерой эффективности алгоритма внутренней сортировки являются число требуемых сравнений значений ключа и число перестановок элементов. Заметим, что поскольку сортировка основана только на значениях ключа и никак не затрагивает оставшиеся поля записей, можно говорить о сортировке массивов ключей.

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

Большую помощь при проведении лекций оказывает использование ноутбука и проектора. Все основные понятия лекции представляются в виде презентации и изображений, выводимых на экране в учебной аудитории. Для графической интерпретации методов используются таблицы, древовидные представления и двоичные деревья, с помощью изображения которых, шаг за шагом, из исходных несортированных данных получается нужный результат. И так для каждого способа. После этого для получения наибольшего эффекта понимания изложенного студентами происходит демонстрация программы, которая наглядно, из введенных несортированных данных, перемещением строго по заданному алгоритму, поэтапно достигает полученной цели. Это и является ключевым моментом в объяснении данной темы.

Для рассмотренных простых методов сортировки существуют точные формулы, вычисление которых дает минимальное, максимальное и среднее число сравнений ключей и пересылок элементов массива. Для оценок сложности усовершенствованных методов сортировки точных формул нет.

На последнем этапе объяснения внутренних методов сортировки рассматривается вопрос сравнения производительности.

В следующей части темы, посвященной сортировке данных, рассматриваются внешние методы.

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

С использованием таблиц и рисунков, происходит наглядное знакомство студентов с методами внешней сортировки: прямое слияние, естественное слияние, сбалансированное многопутевое слияние и многофазная сортировка.

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

Литература

  1. Вирт Н. Алгоритмы+структуры данных = программы: Пер. с англ.-М.Мир,1985.-406 с., ил.
  2. Кнут Д. Искусство программирования для ЭВМ. В семи томах. т.3. Сортировка и поиск. М.: Мир, 1978