- •Вопрос 1) Основные структуры данных.
- •Вопрос 2) Массивы и их свойства.
- •Вопрос 3) Записи
- •Вопрос 4) Множества
- •Операции над множествами
- •Операции отношения.
- •Вопрос 5) Динамические структуры данных;
- •Вопрос 6) Линейные списки.
- •Вопрос 7) Циклические списки
- •Вопрос 8) Стек и его организация
- •Вопрос 9) Очереди и их организация
- •Вопрос 10) Задачи поиска в структурах данных.
- •Вопрос 11) Алгоритм линейного поиска.
- •Вопрос 12) Алгоритм бинарного поиска.
- •Вопрос 13) Алгоритм Кнута, Мориса- Пратта
- •Вопрос 14) Хэширование данных
- •Вопрос 15) сортировка данных
- •15. Сортировка данных
- •1) Сортировка включением
- •2) Сортировка Шелла
- •3) Обменная сортировка
- •4) Сортировка перемешиванием (Шейкерная сортировка)
- •5) Сортировка со слиянием
- •1) Прямое слияние
- •2) Естественное слияние
- •Вопрос 16) Пузырьковая сортировка.
- •17 Вопрос
- •Вопрос 18) Представление графов и деревьев
- •Вопрос 19) Представление бинарных деревьев.
- •Вопрос 20) Представление графов Способы представления графа в информатике Матрица смежности
- •Матрица инцидентности
- •Список рёбер
- •Вопрос 21) Алгоритмы на графах
- •Алгоритм Дейкстры нахождения кратчайшего пути
Вопрос 15) сортировка данных
[data sorting, ordering] — один из этапов обработки данных, упорядочение элементарных данных в последовательности, определяемой значениями некоторых признаков, называемых ключами сортировки. Напр., расположение записей сортируемого массива данных по возрастанию или уменьшению значений величин, содержащихся в массиве. Сортировка массивов данных существенно ускоряет их дальнейшую обработку.Существует 4 вида сортировки: Сортировка вставками, Пузырьковая сортировка, Сортировка Шейкером, Сортировка слиянием.
15. Сортировка данных
Основные определения
Сортировка – это процесс расстановки элементов «в некотором порядке». Элементы размещаются так, чтобы, во-первых, вычисления требующие определенного порядка расположения данных, могли выполняться эффективно, во-вторых, результаты имели осмысленный вид, в третьих, последующие процессы бы пригодные исходные данные.
Записи, поля и ключи. Единица данных, типично обрабатываемая информационными системами, называется записью.
Запись – это совокупность элементов информации о каком-то событии или структуре. Каждый элемент информации в записи, такой как номер служащего, цена единицы товара или валовой объем, называется полем записи. Совокупность полей идентифицирует и описывает то, что представлено в записи. Из записей составляются файлы или наборы данных. Сортировка является процессом перестановки записей или их индексов, при котором их взаимное расположение в файле приводиться в порядок, определяемый некоторым известным ключом. Ключом называется поле, содержащее величину, используемую в правилах упорядочивания файла.
Тип данных ключа должен включать операции сравнения ("=", ">", "<", ">=" и "<="). Задачей сортировки является преобразование исходной последовательности в последовательность, содержащую те же записи, но в порядке возрастания (или убывания) значений ключа.
Метод сортировки называется устойчивым, если при его применении не изменяется относительное положение записей с равными значениями ключа.
Различают сортировку массивов записей, целиком расположенных в основной памяти (внутреннюю сортировку), и сортировку файлов, хранящихся во внешней памяти и не помещающихся полностью в основной памяти (внешнюю сортировку). Для внутренней и внешней сортировки требуются существенно разные методы.
Методы внутренней сортировки
Рассмотрим наиболее известные методы внутренней сортировки, начиная с простых и понятных, но не слишком быстрых, и заканчивая не столь просто понимаемыми усложненными методами.
Естественным условием, предъявляемым к любому методу внутренней сортировки является то, что эти методы не должны требовать дополнительной памяти: все перестановки с целью упорядочения элементов массива должны производиться в пределах того же массива. Мерой эффективности алгоритма внутренней сортировки являются число требуемых сравнений значений ключа (C) и число перестановок элементов (M).
Заметим, что поскольку сортировка основана только на значениях ключа и никак не затрагивает оставшиеся поля записей, можно говорить о сортировке массивов ключей.
Чтобы не привязываться к конкретному языку программирования и его синтаксическим особенностям, мы будем описывать алгоритмы словами и иллюстрировать их на простых примерах.