- •Структуры данных и алгоритмы их обработки (Учебное пособие)
- •Москва 2007
- •1. Структуры данных и алгоритмы 6
- •1.2. Информация и ее представление
- •1.2.1. Природа информации
- •1.2.2. Хранение информации
- •1.2.3. Классификация структур данных
- •1.3. Операции над структурами данных
- •1.4. Порядок алгоритма
- •1.5. Структурность данных и технологии программирования
- •Контрольные вопросы
- •2. Простые структуры данных
- •2.1. Порядковые типы
- •2.2. Целочисленный тип
- •2.3. Символьный тип
- •2.4. Перечисляемый тип
- •2.5. Интервальный тип
- •2.6. Логический тип
- •2.7. Битовый тип
- •2.8. Вещественный тип
- •2.9. Указательный тип
- •Контрольные вопросы
- •3. Объектные типы данных
- •3.1. Объявление и реализация классов
- •Interface
- •Implementation
- •3.2. Директивы видимости
- •3.3. Свойства классов
- •3.4. Структурированная обработка ошибок
- •3.5. Применение объектов
- •Контрольные вопросы
- •4. Статические структуры данных
- •4.1. Векторы
- •4.2. Массивы
- •4.3. Множества
- •4.4. Записи
- •4.5. Таблицы
- •4.6. Операции над статическими структурами
- •4.6.1. Алгоритмы поиска
- •4.6.2. Алгоритмы сортировки
- •Самые медленные алгоритмы сортировки
- •Быстрые алгоритмы сортировки
- •Самые быстрые алгоритмы сортировки
- •Сортировка слиянием
- •Контрольные вопросы
- •5. Полустатические структуры данных
- •5.1. Стеки
- •5.1.1. Стеки в вычислительных системах
- •5.2. Очереди fifo
- •5.2.1. Очереди с приоритетами
- •5.2.2. Очереди в вычислительных системах
- •5.3. Деки
- •5.3.1. Деки в вычислительных системах
- •5.4. Строки
- •5.4.1. Операции над строками
- •5.4.2. Представление строк в памяти
- •3 A b d 8 p q r s t u V w
- •V w ptr nil
- •1 8 П р е д с т а в
- •2 7 ? Л е н и е ?
- •1 8 С т р о к и з
- •1 8 В е н ь я м и
- •1 8 С у п р а в л
- •1 8 Я е м о й д л
- •1 4 И н о й ? ? ? ? nil
- •6.2. Связные линейные списки
- •6.2.1. Машинное представление связных линейных списков
- •Inf next
- •Inf next
- •Inf nil
- •6.2.2. Реализация операций над связными линейными списками
- •Inf next
- •Inf next
- •Inf next
- •Inf next
- •Inf next
- •Inf next
- •Inf next
- •Inf next
- •Inf next
- •Inf next
- •Inf next
- •Inf next
- •6.2.3. Применение линейных списков
- •6.3. Нелинейные разветвленные списки
- •6.3.1. Основные понятия
- •6.3.2. Представление списковых структур в памяти
- •6.3.3. Операции обработки списков
- •6.4. Язык программирования lisp
- •6.5. Управление динамически выделяемой памятью
- •Контрольные вопросы
- •7. Нелинейные структуры данных
- •7.1. Графы и деревья
- •(B) (a) (b) (a)
- •V0 v1 v2 v5 v6 v3 v4 v7 v8 v9 v10 (v0) (v1) (v7) (v8) (v9) (v10) (v3) (v2) (v4) (v5) (v6)
- •7.3. Бинарные деревья
- •7.3.1. Представление бинарных деревьев
- •7.3.2. Прохождение бинарных деревьев
- •7.4. Алгоритмы на деревьях
- •7.4.1. Сортировка с прохождением бинарного дерева
- •7.4.2. Сортировка методом турнира с выбыванием
- •7.4.3. Применение бинарных деревьев для сжатия информации
- •7.4.4. Представление выражений с помощью деревьев
- •7.5. Представление сильноветвящихся деревьев
- •Контрольные вопросы
- •8. Методы ускорения доступа к данным
- •8.1. Хеширование данных
- •8.1.1. Функции хеширования
- •8.1.2. Оценка качества хеш-функции
- •8.1.3. Методы разрешения коллизий
- •8.1.4. Переполнение таблицы и рехеширование
- •8.2. Организация данных для поиска по вторичным ключам
- •8.2.1. Инвертированные индексы
- •8.2.2. Битовые карты
- •Контрольные вопросы
- •Листинги рабочих примеров
- •1. Создание и управление списковыми объектами
- •Interface
- •Implementation
- •Interface
- •Implementation
- •3. Моделирование работы стека
- •Interface
- •Implementation
- •Interface
- •Implementation
- •4. Создание и редактирование бинарных деревьев
- •5. Создание и редактирование сильноветвящихся деревьев
- •Задания для самостоятельной работы
- •Литература
- •144Кафедра Вычислительной Техники и Программирования Московского Государственного Открытого Университета
4.6.2. Алгоритмы сортировки
Сформулируем задачу сортировки для общего случая следующим образом: имеется некоторое неупорядоченное входное множество ключей и требуется получить выходное множество тех же ключей, упорядоченных по возрастанию или убыванию. Из всех задач программирования сортировка, возможно, имеет самый богатый выбор алгоритмов решения. Назовем некоторые факторы, влияющие на выбор алгоритма (помимо порядка алгоритма).
Имеющийся ресурс памяти: должно ли входное и выходное множество располагаться в разных областях памяти или выходное множество может быть сформировано на месте входного. В последнем случае имеющаяся область памяти должна в ходе сортировки динамически перераспределяться между входным и выходным множествами. Для одних алгоритмов это связано с большими затратами, для других – с меньшими.
Исходная упорядоченность входного множества: во входном множестве (даже если оно сгенерировано датчиком случайных чисел) могут попадаться уже упорядоченные участки. В предельном случае входное множество может оказаться уже упорядоченным. Одни алгоритмы не учитывают исходной упорядоченности и требуют одного и того же времени для сортировки любого (в том числе уже упорядоченного) множества данного объема, другие выполняются тем быстрее, чем лучше упорядоченность на входе.
Временные характеристики операций: при определении порядка алгоритма время выполнения обычно считается пропорциональным числу сравнений ключей. Ясно, что сравнение числовых ключей выполняется быстрее, чем строковых; операции пересылки, характерные для некоторых алгоритмов, выполняются тем быстрее, чем меньше объем записи, и т.п. В зависимости от обрабатываемых данных может быть выбран алгоритм, обеспечивающий минимизацию числа тех или иных операций.
Сложность алгоритма: простой алгоритм требует меньшего времени для его реализации и вероятность ошибки меньше. При промышленном изготовлении программного продукта требования соблюдения сроков разработки и надежности могут даже превалировать над требованиями эффективности функционирования.
Устойчивость алгоритма: все алгоритмы можно разделить на два типа – устойчивые и неустойчивые. К устойчивой сортировке относятся те алгоритмы, которые при наличии в исходном наборе данных нескольких равных элементов в отсортированном наборе оставляют их в том же порядке, в котором они были изначально. Например, в исходном наборе находятся три элемента с одинаковым значением 42. Пусть элемент A находится в позиции 12, элемент B – в позиции 234, C – 3456. После выполнения устойчивой сортировки они будут находиться в последовательности A,B,C. Неустойчивая сортировка не гарантирует сохранение исходного взаимного порядка, и расположение может быть B,C,A или C,A,B.
Разнообразие алгоритмов сортировки требует некоторой их классификации. Один из известных методов классификация ориентирован на логические характеристики применяемых алгоритмов. Согласно методу любой алгоритм сортировки использует одну из следующих четырех стратегий (или их комбинацию).
Стратегия выборки. Из входного множества выбирается следующий по критерию упорядоченности элемент и включается в выходное множество на место, следующее по номеру.
Стратегия включения. Из входного множества выбирается следующий по номеру элемент и включается в выходное множество на то место, которое он должен занимать в соответствии с критерием упорядоченности.
Стратегия распределения. Входное множество разбивается на ряд подмножеств (возможно, меньшего объема) и сортировка ведется внутри каждого такого подмножества.
Стратегия слияния. Выходное множество получается путем слияния небольших упорядоченных подмножеств.
Другим методом классификации является группирования алгоритмов по скорости выполнения. Именно такой метод будет использован при дальнейшем изложении, т.к. он в наибольшей степени отвечает практической применимости тех или иных алгоритмов. Алгоритмы рассмотрены для случая упорядочения по возрастанию ключей. В большинстве примеров в качестве процедуры сортировки будет использоваться следующий прототип:
{ Прототип процедуры сортировки }
TSortProc=procedure(aList:TList;
aFirst, aLast: Integer; aCompare: TCompareFunc);
Первым параметром следует список, затем границы сортируемой области и функция сравнения.