- •Структуры и алгоритмы обработки данных
- •Алгоритмы. Основные определения
- •От задачи к программе
- •Написание программы.
- •Типы данных, структуры данных и абстрактные типы данных
- •Указатели и курсоры
- •Время выполнения программ
- •Измерение времени выполнения программы
- •Степень (порядок) роста
- •Вычисление времени выполнения программ
- •Линейные абстрактные типы данных атд «Список»
- •Реализация списков посредством массивов
- •Реализация списков с помощью указателей
- •Атд «Стек»
- •Атд «Очередь»
- •Реализация очередей с помощью циклических массивов
- •Нелинейные абстрактные типы данных Деревья
- •Порядок узлов
- •Прямой, обратный и симметричный обходы дерева
- •Помеченные деревья и деревья выражений
- •Представление деревьев с помощью массивов
- •Специальные виды множеств атд “Дерево двоичного поиска”
- •Атд "Словарь", основанный
- •Представление ориентированных графов
- •Атд для ориентированных графов
- •Задача нахождения кратчайшего пути
- •Int **c, // массив стоимостей
- •Int *d) // массив кратчайших
- •Остовные деревья минимальной стоимости
- •Обход графов
- •Поиск в ширину
- •Поиск в глубину
- •Сортировка
- •Простые схемы сортировки Метод «пузырька»
- •Сортировка вставками
- •Быстрая сортировка
- •Пирамидальная сортировка
- •«Карманная» сортировка
- •Порядковые статистики
- •Методы разработки алгоритмов. Типы алгоритмов
- •Алгоритмы «разделяй и властвуй» (метод декомпозиции)
- •Баланс подзадач
- •Динамическое программирование
- •Перемножение нескольких матриц
- •Шаг 1: строение оптимальной расстановки скобок
- •Шаг 2: рекуррентное соотношение
- •Шаг 3: вычисление оптимальной стоимости
- •Void MatrixChainOrder(int n, // кол-во матриц
- •Int p[], // размеры матриц
- •Int **s) // оптимальное k
- •Шаг 4: построение оптимального решения
- •Int **s, // таблица, полученная
- •Int I, // индексы
- •Когда применимо динамическое программирование?
- •Оптимальность для подзадач
- •Перекрывающиеся подзадачи
- •«Жадные» алгоритмы
- •"Жадные" алгоритмы как эвристики
- •Когда применим жадный алгоритм?
- •Принцип жадного выбора
- •Оптимальность для подзадач
- •Поиск с возвратом
- •Функции выигрыша
- •Метод ветвей и границ
- •Структуры данных и алгоритмы для внешней памяти
- •Внешняя сортировка
- •Хранение данных в файлах
- •Простая организация данных
- •Хешированные файлы
- •Индексированные файлы
- •Содержание
- •Глава I. Линейные абстрактные типы данных 31
- •Глава II. Сортировка 108
-
Сортировка
Сортировкой, или упорядочиванием списка объектов называется расположение этих объектов по возрастанию или убыванию согласно определенному линейному отношению порядка, такому как отношение « » для чисел.
Сортировка бывает двух типов внутренняя и внешняя.
При внутренней сортировке все сортируемые данные помещаются в оперативную память компьютера, где можно получить доступ к данным в любом порядке (т.е. используется модель памяти с произвольным доступом).
Внешняя сортировка применяется тогда, когда объем упорядочиваемых данных слишком большой, чтобы все данные можно было поместить в оперативную память. Здесь узким местом является механизм перемещения больших блоков данных от устройств внешнего хранения данных в оперативную память и обратно.
Тот факт, что физически непрерывные данные надо для удобного перемещения организовывать в блочную структуру, заставляет нас применять отличные от внутренних методы сортировки.
Будем предполагать, что сортируемые объекты являются записями, содержащими одно или несколько полей. Одно из полей, называемое ключом, имеет такой тип данных, что на нем определено отношение линейного порядка.
Задача сортировки состоит в упорядочивании последовательности записей таким образом, чтобы значения ключевого поля составляли неубывающую последовательность.
Т.е. записи r1,r2,…,rn со значениями ключей k1,k2,…,kn надо расположить в порядке
,
таким, что
.
Записи с одинаковыми значениями ключей располагаются рядом друг с другом в произвольном порядке.
Для анализа эффективности алгоритмов сортировки используются различные критерии: наиболее общей мерой времени выполнения является количество шагов алгоритма, необходимых для упорядочивания n записей. Другой общей мерой служит количество сравнений между значениями ключей, выполняемых при сортировке списка из n записей.
Эта мера особенно информативна, когда ключи являются строками символов, и поэтому самым трудоемким оператором будет оператор сравнения ключей.
Рассмотрим примеры внутренних сортировок.
Простые схемы сортировки Метод «пузырька»
Представим, что записи, подлежащие сортировке, хранятся в массиве. Расположенном вертикально.
Записи с малыми значениями ключевого поля более «легкие» и всплывают вверх наподобие пузырька.
При первом проходе вдоль массива, начиная проход снизу, берется первая запись массива и ее ключ поочередно сравнивается с ключами последующих записей. Если встречается запись с более «тяжелым» ключом, то эти записи меняются местами. При встрече с записью с более «легким» ключом эта запись становится «эталоном» для сравнения, и все последующие записи сравниваются с ним.
В результате запись с наименьшим значением ключа окажется в самом верху массива.
Во время второго прохода массива находится запись со вторым по величине ключом, которая помещается под записью, найденной при первом проходе и т.д.
Отметим, что во время второго и последующих проходов вдоль массива нет необходимости просматривать записи, найденные за предыдущие проходы, так как они имеют ключи, меньшие, чем у оставшихся записей.
Алгоритм «пузырька»
for (i=0; I < n-1; i++)
for(j=1; j < i+1; j++)
if(a[j].key < a[j-1].key)
{
temp=a[j];
a[j]=a[j-1];
a[j-1]=temp;
}
Время работы алгоритма порядка О(n2). Применим `только к небольшим массивам.