ЛЕКЦИЯ 24. ОБЗОР МАТЕРИАЛА

Цели и задачи лекции:обзор материала по дисциплине за семестр.

Основные вопросы:Концепция типов данных. Линейные структуры данных:списки, стеки, очереди, деки. Нелинейные структуры данных: нелинейные списки, деревья, графы. Поиск данных: последовательный поиск, быстрые методы поиска, поиск с использованием древовидных структур. Организация данных в файлах.

КОНСПЕКТ ЛЕКЦИЙ ПО ДИСЦИПЛИНЕ

«СТРУКТУРЫ И АЛГОРИТМЫ ОБРАБОТКИ ДАННЫХ»

(Часть 2. Семестр 4)

Для подготовки бакалавров по направленям:

654600 – «Информационные системы и технологии»

ЛЕКЦИЯ 1. ЗАДАЧИ И КЛАССИФИКАЦИЯ МЕТОДОВ СОРТИРОВКИ. МЕТОДЫ ОБМЕННОЙ СОРТИРОВКИ, ШЕЙКЕРНАЯ СОРТИРОВКА.

Цель лекции: ознакомить с классификацией методов сортировки; изучить методы обменной сортировки, шейкерной сортировки

Рассматриваемые вопросы: задачи сортировки, классификация методов сортировки, сортировка обменами, шейкерная сортировка.

Задачи сортировки

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

Критерии качества и классификация методов сортировки. Основным критерием качества методов сортировки является сложность алгоритма O(n).

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

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

При сортировке последовательностей, уже упорядоченных по некоторым вторичным ключам методы сортировки разделяют на устойчивые и неустойчивые. Метод сортировки называется устойчивым, если в процессе сортировки относительное расположение элементов с равными ключами не изменяется, в неустойчивых методах данное условие может не выполняться.

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

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

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