- •Структура и алгоритмы обработки данных
- •Понятие алгоритма и структуры данных.
- •Анализ сложности и эффективности алгоритмов и структур данных.
- •Данные числовых типов. Данные целочисленного типа. Данные вещественного типа.
- •Данные числовых типов. Операции над данными числовых типов. Данные символьного типа.
- •Данные логического типа. Данные типа указатель.
- •Линейные структуры данных. Массив.
- •Линейные структуры данных. Строка.
- •Линейные структуры данных. Запись.
- •Линейные структуры данных. Множество.
- •Линейные структуры данных. Таблица.
- •Линейные структуры данных. Линейные списки. Циклические списки.
- •Линейные структуры данных. Разреженные матрицы.
- •Линейные структуры данных. Стек.
- •Линейные структуры данных. Очередь.
- •Линейные структуры данных. Дек.
- •Нелинейные структуры данных. Мультисписки. Слоенные списки.
- •Нелинейные структуры данных. Графы. Спецификация.
- •Нелинейные структуры данных. Графы. Реализация.
- •Нелинейные структуры данных. Деревья. Общие понятия.
- •Нелинейные структуры данных. Деревья. Обходы деревьев.
- •Нелинейные структуры данных. Деревья. Спецификация двоичных деревьев. Реализация. Основные операции.
- •Файлы. Организация.
- •Файлы. В-деревья. Представление файлов в-деревьями.
- •Файлы. В-деревья. Основные операции.
- •Файлы. В-деревья. Общая оценка в-деревьев.
- •Методы разработки алгоритмов. Метод декомпозиции. Динамическое программирование.
- •Методы разработки алгоритмов. Поиск с возвратом. Методы ветвей и границ.
- •Алгоритмы поиска. Поиск в линейных структурах.
- •Алгоритмы поиска. Хеширование данных.
- •Алгоритмы поиска. Использование деревьев в задачах поиска.
- •Алгоритмы поиска. Поиск в тексте.
- •Алгоритмы кодирования (сжатия) данных.
- •Алгоритмы сортировки. Сортировка подсчетом. Сортировка простым включением.
- •Алгоритмы сортировки. Сортировка методом Шелла. Сортировка простым извлечением.
- •Алгоритмы сортировки. Древесная сортировка. Сортировка методом пузырька.
- •Алгоритмы сортировки. Быстрая сортировка (Хоара). Сортировка слиянием.
- •Алгоритмы сортировки. Сортировка распределением. Сравнение алгоритмов внутренней сортировки.
- •Алгоритмы обхода графа. Поиск в глубину.
- •Алгоритмы обхода графа. Поиск в ширину (волновой алгоритм).
Алгоритмы сортировки. Сортировка подсчетом. Сортировка простым включением.
Основные виды сортировки
Сортировка – это процесс упорядочения некоторого множества элементов, на котором определены отношения порядка >, <, ≥, ≤, =. Когда говорят о сортировке, подразумевают упорядочение множества элементов по возрастанию или убыванию.
Алгоритмы сортировки имеют большое практическое применение. Их можно встретить почти везде, где речь идет об обработке и хранении больших объемов информации.
Традиционно различают внутреннюю сортировку, в которой предполагается, что данные находятся в оперативной памяти, и важно оптимизировать число действий программы, и внешнюю, в которой данные хранятся на внешнем устройстве с медленным доступом и, прежде всего, надо снизить число обращений к этому устройству.
Алгоритмы внутренней сортировки
При дальнейшем рассмотрении внутренней сортировки определим, что множество данных, которые упорядочиваются, описывается как массив фиксированной длины:
A: array[1..n] of ItemType;
Сортировка подсчетом
Суть метода заключается в том, что на каждом шаге подсчитывается, в какую позицию результирующего массива B надо записать очередной элемент исходного массива A
Этот алгоритм всегда имеет временную сложность, пропорциональную O(n2) (два вложенных цикла, зависящих от n линейно и не зависящих от порядка элементов) и пространственную сложность, пропорциональную O(n) (результирующий массив). Также следует отметить, что данный алгоритм сохраняет порядок элементов с одинаковыми значениями.
Сортировка простым включением
В этой сортировке массив делится на две части: отсортированную и неотсортированную. На каждом шаге берется очередной элемент из неотсортированной части и «включается» в отсортированную часть массива
Этот алгоритм также имеет максимальную и среднюю временную сложности, пропорциональные O(n2), но в случае исходно отсортированного массива внутренний цикл не будет выполняться ни разу, поэтому метод имеет временную сложность Tmin(n), пропорциональную O(n). Можно заметить, что метод использует любой частичный порядок, и чем в большей степени массив исходно упорядочен, тем быстрее он закончит работу. В отличие от предыдущего метода, этот не требует дополнительной памяти, но сохраняет порядок элементов с одинаковыми значениями.
Алгоритмы сортировки. Сортировка методом Шелла. Сортировка простым извлечением.
Метод Шелла является усовершенствованием метода простого включения, который основан на том, что включение использует любой частичный порядок. Но недостатком простого включения является то, что во внутреннем цикле элемент фактически сдвигается на одну позицию. И так до тех пор, пока он не достигнет своего места в отсортированной части.
Как показывают теоретические выкладки сортировке методом Шелла требуется в среднем 1,66n перемещений. Порядок элементов влияет на количество итераций внутреннего цикла while. Дополнительной памяти данный алгоритм не требует, но и не гарантирует сохранение порядка элементов с одинаковыми значениями.
Сортировка простым извлечением.
В этом методе массив также делится на уже отсортированную часть A[i+1], A[i+1], ..., A[n] и еще не отсортированную A[1], A[2], ..., A[i]. Но здесь из неотсортированной части на каждом шаге извлекается максимальный элемент, просматривая ее заново на каждом шаге. Этот элемент будет минимальным элементом отсортированной части, так как все большие его элементы были извлечены на предыдущих шагах, поэтому ставим извлеченный элемент в начало отсортированной части, точнее меняем его с A[i] местами
Простое извлечение во всех случаях имеет временную сложность, пропорциональную O(n2) (два вложенных цикла, зависящих от n линейно и не зависящих от порядка элементов). Также следует отметить, что данный алгоритм не требует дополнительной памяти и не гарантирует сохранение порядка элементов с одинаковыми значениями.