- •Основные понятия структур
- •Концепция типа данных, простейшие типы данных, стандартные типы данных, органические типы (диапазоны)
- •Статические и полустатические структуры данных
- •2. 1. Массив.
- •2. 2. Запись, записи с вариантами.
- •2. 3. Стек.
- •5. Очередь
- •2. 7. Отображение
- •Динамические структуры данных
- •3.1. Односвязные списки, кольцевой список
- •3. 2. Двусвязный список, кольцевой двусвязный список
- •4. Рекурсивные алгоритмы
- •4. 1. Деревья, бинарные деревья, представление деревьев
- •4. 2. Основные операторы, используемые для работы с деревьями
- •4. 3. Алгоритм создания дерева бинарного поиска
- •4. 4. Прохождение бинарных деревьев
- •1. Прохождение в прямом порядке
- •3. Прохождение в обратном порядке
- •4. 5. Когда рекурсию использовать не нужно
- •4. 6. Рекурсивные программы, примеры
- •5. Поиск
- •5. 1. Линейный поиск
- •5. 2. Двоичный поиск
- •5. 3. Индексно-последовательный поиск
- •5. 3. Поиск в таблице
- •5. 4. Поиск прямой строки
- •Поиск по бинарному дереву
- •Алгоритм кнута, Морриса и Пратта
- •5. 6. Алгоритм Боуера и Мура
- •Сортировка. Необходимые определения и классификация сортировок. Сортировки прямого включения и выбора. Их эффективность Необходимые определения и классификация сортировок.
- •Сортировка методом прямого включения
- •Эффективность алгоритма сортировки прямого включения
- •Сортировка методом прямого выбора
- •Эффективность алгоритма сортировки прямого выбора
- •Сортировка прямого обмена. Её эффективность
- •Эффективность алгоритма сортировки прямого обмена
- •Улучшенные методы сортировки. Быстрая сортировка. Её эффективность.
- •Быстрая сортировка
- •Принцип работы быстрой сортировки
- •Пример работы быстрой сортировки
- •Блок-схема быстрой сортировки
- •Улучшенные методы сортировки. Сортировка шелла. Её эффективность. Сортировка шелла
- •Принцип работы сортировки шелла и необходимые расчёты для её реализации
- •Пример расчёта последовательности расстояний для малых массивов
- •Пример работы сортировки шелла
- •Принцип работы пирамидальной сортировки
- •Пример работы пирамидальной сортировки
- •Представление графов
- •Нахождение кратчайших путей между парами вершин
Сортировка. Необходимые определения и классификация сортировок. Сортировки прямого включения и выбора. Их эффективность Необходимые определения и классификация сортировок.
Сортировка – это расположение данных в памяти в регулярном виде по их ключам. Так что при обработке данных важно знать информационное поле данных и размещение их в машине. Поэтому различают внутреннюю (сортировка в оперативной памяти) и внешнюю сортировки (сортировка во внешней памяти). Регулярность расположения элементов – это возрастание (убывание) значения ключа от начала к концу в массиве.
Если сортируемые записи занимают большой объем памяти, то их перемещение требует больших затрат. Для того чтобы их уменьшить, используют метод сортировки таблицы адресов. Этот метод применяют в таблице адресов ключей. Производят перестановку указателей, т.е. Сам массив не перемещается. При сортировке могут встретиться и одинаковые ключи. В этом случае одинаковые ключи желательно расположить после сортировки в том же порядке, что и в исходном файле. Этот принцип используется для устойчивой сортировки.
Эффективность сортировки можно рассматривать с нескольких критериев:
1) время, затрачиваемое на сортировку;
2) объем оперативной памяти, требуемой для сортировки;
3) время, затраченное программистом на написание программы.
Время, затраченное на сортировку, пропорционально количеству сравнений при выполнении сортировки и количеству перемещений элементов.
Считается, что порядок числа сравнения при сортировке может находиться в пределах от о(nlogn) до о(n2), где о(n) - идеальный и недостижимый случай.
Методы сортировки можно классифицировать примерно так:
1) строгие (прямые) методы (их эффективность примерно одинакова):
прямого включения;
прямого выбора;
прямого обмена;
2) улучшенные методы.
Сортировка методом прямого включения
В жизни принцип данной сортировки присутствует при раскладывании пасьянсов, уборки квартиры, когда необходимо расположить кучу смешанных вещей в должном порядке и т.д. Очень естественный способ сортировки был применён и к упорядочиванию данных.
Элементы мысленно делятся на уже готовую последовательность a1,...,ai-1 и исходную последовательность. В готовой последовательности элементы располагаются в заданном порядке (по убыванию или по возрастанию). А в исходной последовательности располагаются элементы, которые и нужно отсортировать. При каждом шаге элементы исходной последовательности уменьшаются на единицу, а готовая увеличивается на единицу. Это происходит из-за того, что из исходной последовательности извлекается i-й элемент и перекладывается в готовую последовательность, при этом он вставляется на нужное место среди элементов готовой последовательности.
Рассмотрим пример сортировки методом прямого включения на последовательности элементов: 10, 3, 11, 8, 2, 15, 44, 9 (табл. 11.1). Необходимо её отсортировать по возрастанию.
Сначала готовая последовательность не имеет элементов. На первом шаге первый элемент исходной последовательности – это 10, становится первым элементом готовой последовательности. Далее второй шаг: элемент 3 из исходной последовательности помещается в готовую. Это происходит так. Если элемент больше 10, то он остаётся на своём месте, а если меньше, то 10 сдвигается на единицу вправо и на её место ставится элемент. Так как 3<10, то готовая последовательность теперь будет иметь вид: 3, 10, а исходная – 11, 8, 2, 15, 44, 9. Далее на третьем шаге из исходной последовательности выбирается 11 и помещается в готовую последовательность. Сначала 11 сравнивается с 10, и так как 11>10, то 11 остаётся на месте. Исходная последовательность теперь равна: 8, 2, 15, 44, 9. Последующие шаги производятся аналогичным образом.
Таблица 11.1
Принцип работы сортировки прямым включением
Шаг |
Готовая последовательность |
Исходная последовательность |
1 |
10 |
3, 11, 8, 2, 15, 44, 9 |
2 |
3, 10 |
11, 8, 2, 15, 44, 9 |
3 |
3, 10, 11 |
8, 2, 15, 44, 9 |
4 |
3, 8, 10, 11 |
2, 15, 44, 9 |
5 |
2, 3, 8, 10, 11 |
15, 44, 9 |
6 |
2, 3, 8, 10, 11, 15 |
44, 9 |
7 |
2, 3, 8, 10, 11, 15, 44 |
9 |
8 |
2, 3, 8, 9, 10, 11, 15, 44 |
|
Число шагов в данной сортировке (табл. 11.1) равно числу элементов в сортируемой последовательности, т.е. 8 шагов = 8 элементов.
Существуют два способа реализации данного метода – это без барьера (рис. 11.1) и с барьером (рис. 11.2).