- •Понятие «сортировка». Устойчивость сортировки.
- •Задача сортировки.
- •Понятие «ключевое поле» в сортировке.
- •Понятие внутренней сортировки.
- •Понятие внешней сортировки.
- •Причины изучения алгоритмов сортировки.
- •Группы алгоритмов внутренней сортировки.
- •Основные идеи методов сортировок с помощью вставок.
- •2)Улучшение метода простых вставок:
- •Сортировка методом простых вставок.
- •Основные идеи методов сортировок с помощью выбора.-min эл.
- •Сортировка с помощью метода прямого выбора.
- •Основные идеи методов сортировки с помощью обмена.
- •Сортировка методом Шелла.
- •Быстрая сортировка.-разобрать
- •Понятие эффективности алгоритмов и программ.
- •Виды эффективности алгоритмов программ.
- •Порядок сложности алгоритма.
- •Понятие «доминирующая» функция, «асимптотически доминирующая» функция.
- •Правила определения сложности функции.
- •Доминирование функций друг над другом.-разобрать хрень!!!
- •Понятие алгоритма полиноминальной сложности.
- •Понятие алгоритма неполиноминальной сложности.
- •Вопрос 27.
- •Проблемы реализации np-сложных алгоритмов.
- •Вопрос 27.
- •Соответствие между скоростью выполнения алгоритма и его сложностью.
- •Анализ лучшего, худшего и среднего случаев поведения алгоритма.
- •31* Ограниченность о-анализа.
- •Пространственная сложность программы.
- •Взаимосвязь различных типов сложности.
- •Контрольные замеры.
- •Файлы. Их организация и обработка.
- •Стоимость операций с вторичной памятью.
- •Внешняя сортировка. Особенности внешней сортировки.
- •Понятие «серия», «слияние», «хвост», «фаза», «этап» в алгоритмах внешней сортировки.
- •38* Алгоритм 2-х фазной сортировки прямым слиянием.
- •Алгоритм однофазной сортировки прямым слиянием.
- •Алгоритм сортировки «естественным слиянием».
- •Ускорение сортировок прямым слиянием.
- •Задача поиска.
- •Классификация методов поиска.
- •Связь задач сортировки и поиска.
- •Последовательный поиск.
- •Быстрый последовательный поиск.
- •Последовательный поиск в упорядоченной таблице. Поиск путем сравнения ключей.-херня!
- •Бинарный поиск. Интерполяционный поиск.
- •Хеширование Выбор хеш-функций.
- •Хеширование. Разрешение коллизий.
ВОПРОСЫ К ЭКЗАМЕНУ ПО КУРСУ «Структуры и алгоритмы обработки данных»
Понятие «сортировка». Устойчивость сортировки.
Сортировкой списка объектов наз. такую перестановку этих объектов, при кот. они располагаются в некотором определенном порядке. Цель сортировки – облегчить поиск нужного объекта в отсортированном списке.
Важная область применения сортировки:
поиск общих элементов в 2-х и более массивах
решение задачи группирования Цель: есть некоторое кол-во объектов, расположены случ. образом. Нужно собрать вместе объекты, у кот. некоторый признак имеет общее значение
поиск информации по значению ключей.
Задача сортировки: сортировки подлежат некоторые объекты.
Предметная область, в кот. есть объекты. Каждый объект имеет некие данные (в общем случае – некоторая запись с полями). Чтобы выделить некий конкретный объект среди множества объектов, нужно выделить некий признак в записи, кот. позволяется:
отсылать нас к нужному нам объекту.
даст нам возможность выделить запись об этом объекте среди других объектов.
С этой целью в записи предусматривается спец. поле, кот носит название ключевое поле или ключ. В общем случае задача сортировки: есть N записей b1 … bn. В каждой записи bj есть ключевое поле kj, кот. управляет процем сортировки.
Помимо ключ. поля запись может иметь много других полей, но они не влияют на процесс сортировки. Поэтому в алгоритмах сортировки речь идет о ключевом поле, а все остальные поля опускаются.
Задача сортировки состоит в том, что нужно найти такую перестановку записей b1… bn со значениями ключей k1… kn, после кот. ключи записей расположились бы в порядке неубывания.
Kb1 <= Kb2… <= Kbn
Метод сортировки наз. устойчивым, если в процессе сортировки относительное положение элементов не изменяется.
Устойчивость сортировки бывает необходимой тогда, когда элементы уже были упорядочены по некоторым вторичным ключа, по кот. сортировка была произведена до этого.
Задача сортировки.
1й вопрос ОСНОВНОЙ ОТВЕТ: Задача сортировки состоит в том, что нужно найти такую перестановку записей b1… bn со значениями ключей k1… kn, после кот. ключи записей расположились бы в порядке неубывания.
Kb1 <= Kb2… <= Kbn
Понятие «ключевое поле» в сортировке.
1й вопрос.
ОСНОВНОЙ ОТВЕТ: С этой целью в записи предусматривается спец. поле, кот носит название ключевое поле или ключ. В общем случае задача сортировки: есть N записей b1 … bn. В каждой записи bj есть ключевое поле kj, кот. управляет процем сортировки.
Помимо ключ. поля запись может иметь много других полей, но они не влияют на процесс сортировки. Поэтому в алгоритмах сортировки речь идет о ключевом поле, а все остальные поля опускаются.
Понятие внутренней сортировки.
Все методы сортировки делятся на 2 класса.
внутренняя – сортировка массивов
внешняя – сортировка файлов
ОП – быстрый доступ. Мало объема. Случайный доступ к данным.
Внешняя – медленная. Много. Последовательный доступ к данным.
Внутренняя сортировка.
Внутренняя сортировка только в рамках исходного массива. Никаких дополнительных!!!
Среди внутренних методов сортировки без введения доп. структур дан. (массивов) можно в соответствии с принципами их работы выделить 3 группы семейств алгоритмов:
сортировка с помощью вставок
с помощью выбора
с помощью обмена
Для работы всех алгоритмов нужно ввести некоторую вспомогательную переменную. Она нужна для временного хранения значения элемента при перестановке элементов. Пусть это Х.