- •Оглавление
- •Цикл жизни программного обеспечения
- •Начальные этапы разработки по
- •Общие требования к методологии и проектированию по
- •Качество и надежность программного обеспечения
- •Показатели качества
- •Сложность комплексов программ
- •Надежность комплексов программ
- •Критерии надежности
- •Сбой, отказ, восстановление
- •Алгоритмы сортировки
- •Введение
- •Внутренняя сортировка
- •Сравнение эффективности алгоритмов сортировки
- •Простая сортировка вставками
- •Быстрая сортировка Хоара. Сортировка методом пузырька
- •Сортировка методом «турнира с выбыванием»
- •Реализация сортировки вставками. Алгоритм Шелла.
- •Сортировка слиянием. Поразрядная сортировка
- •Поиск данных
- •Введение в поиск данных
- •Последовательный поиск
- •Поиск в упорядоченной таблице
- •Бинарный поиск
- •Поиск по дереву
- •Вставка в дерево бинарного поиска
- •Удаление из дерева бинарного поиска
- •Хеширование
- •Разрешение коллизий при хешировании методом открытой адресации
- •Выбор хеш-функции
- •Объектно-ориентированное программирование
- •Введение в объектно-ориентированное программирование
- •Инкапсуляция
- •Полиморфизм
- •Конструкторы и деструкторы
- •Наследование
- •Объединения, встраиваемые функции
- •Указатели и адреса
- •Программирование параллельных вычислений
- •Введение
- •Сети. Родитель сети
- •Синхронизация процессов
- •Литература
Внутренняя сортировка
Существует, по крайней мере, пять широко известных способов, применяемых в алгоритмах внутренней сортировки.
Вставка. На i-м этапе i-е имя помещается на надлежащее место c i-1 уже отсортированными именами.
Обмен. Два имени, расположение которых не соответствует порядку, меняются местами (обмен). Эта процедура повторяется, пока существуют такие пары.
Выбор. На i-м этапе из неотсортированных имен выбирается i-е наибольшее (наименьшее) имя и помещается на соответствующее место.
Распределение. Имена распределяются по группам, и содержимое групп затем объединяется таким образом, чтобы частично отсортировать таблицу; процесс повторяется до тех пор, пока таблица не будет отсортирована полностью.
Слияние. Таблица делится на подтаблицы, которые сортируются по отдельности и затем сливаются в одну.
Эти классы нельзя назвать ни взаимоисключающими, ни исчерпывающими. Они
удобны для классификации алгоритмов сортировки. В рассматриваемых алгоритмах имена образуют последовательность x1, …, xn. Значением xi является любое текущее имя i позиции последовательности. В каждом из рассматриваемых алгоритмов будем считать, что имена нужно сортировать на месте, т.е. перемещение имен должно происходить внутри последовательности x1, …, xn. При этом существует одна или две дополнительные ячейки, в которых временно размещается значение имени.
Ограничение «сортировка на месте» основано на предположении, что число имен настолько велико, что во время сортировки не допускается перенос их в другую область памяти.
Сравнение эффективности алгоритмов сортировки
Чтобы получить некоторое представление об ожидаемой эффективности, рассмотрим задачу сортировки с теоретической точки зрения.
Один из способов оценки эффективности алгоритмов сортировки состоит в подсчете числа сравнений имен ‘xi: xj’ за время сортировки. Эта характеристика не всегда является определяющей, но для большинства алгоритмов она является хорошей мерой производимой работы. Будем рассматривать алгоритмы, основанные на абстрактном линейном упорядочении пространства имен: для любой пары имен xi, xj при i j либо xi < xj, либо xi > xj.
Любой такой алгоритм можно представить в виде расширенного бинарного дерева решений, в котором каждый внутренний узел соответствует сравнению имен, и каждый лист (внешний узел) — исходу алгоритма. Это дерево можно рассматривать как блок-схему алгоритма сортировки, в котором все циклы «размотаны» и показаны только сравнения имен.
Пример. Рассмотрим сортировку элементов массива {x1, x2, x3} с использованием бинарного дерева.
Рис. 3.3. Бинарное дерево решений для сортировки трех имен
В любом таком дереве решений каждая перестановка определяет единственный путь от корня к листу. Листья, соответствующие разным перестановкам, должны быть разными. Тогда ясно, что в дереве решений для сортировки n имен должно быть по крайней мере n! листьев (n! — количество перестановок из n).
Заметим, что высота дерева решений h равна числу сравнений, требующихся алгоритму в наихудшем случае.
Поскольку бинарное дерево высоты h может иметь не больше 2h листьев, заключаем что
т.к.
Таким образом, любой алгоритм сортировки, основанный на сравнении имен, в наихудшем случае потребует не меньше n lg n сравнений.
Длина внешних путей дерева решений равна сумме всех расстояний от корня до листьев, деление ее на n! дает среднее число сравнений для соответствующего алгоритма.