Сортировка слиянием - раздел Образование, Основные операции при работе с деревьями
Рассматривается Сортировка Слиянием (Mergesort), Которая Явля...
Рассматривается сортировка слиянием (mergesort), которая является дополнением быстрой сортировки в том, что она состоит из двух рекурсивных вызовов с последующей процедурой слияния.
Одним из наиболее привлекательных свойств сортировки слиянием является тот факт, что она сортирует массив, состоящий из N элементов, за время, пропорциональное NlogN, независимо от характера входных данных.
Сортировка слиянием — это устойчивая сортировка, и данное обстоятельство склоняет чашу весов в ее пользу в тех приложениях, в которых устойчивость имеет важное значение.
Другое свойство сортировки слиянием, которое приобретает важное значение в некоторых ситуациях, является тот факт, что сортировка слиянием обычно реализуется таким образом, что она осуществляет, в основном, последовательный доступ к данным (один элемент за другим).
Имея два упорядоченных входных массива, их можно объединить в один упорядоченный выходной массив просто отслеживая наименьший элемент в каждом массиве и входя в цикл, в котором меньший из двух элементов, наименьших в своих массивах, переносится в выходной массив; процесс продолжается до тех пор, пока оба входных массива не будут исчерпаны.
Листинг: Алгоритм сортировки слиянием
//-------------------------------------------------------------
// Шаблон move задает вспомогательную функцию, которая просто
// переносит элементы массива из одного фрагмента массива
// в другой фрагмент того же самого или другого массива.
// - Key - класс, задающий тип элементов массива;
// - src - исходный фрагмент массива;
// - sLow, sHigh - индексы, задающие диапазон в исходном массиве;
// - dst - результирующий фрагмент массива;
// - dLow - индекс, задающий нижнюю границу результирующего массива.
//-------------------------------------------------------------
template <class Кеу>
void move(Key * src, int sLow, int sHigh, Key * dst, int dLow) {
for (int pSrc = sLow, pDst = dLow; pSrc <= sHigh;) { dst[pDst++] = src[pSrc++];
}
}
//-------------------------------------------------------------
// Шаблон mergeSort задает функцию сортировки элементов
// массива методом последовательного слияния.
// - Key - класс, задающий тип элементов массива;
// - array - упорядочиваемый массив;
// - low, high - индексы, задающие диапазон сортировки.
//-------------------------------------------------------------
template <class Кеу>
void mergeSort(Key * array, int low, int high) {
// Предполагается, что в начале работы low <= high
// В результате сортировки получается упорядоченный фрагмент
// массива в диапазоне от low до high
int n = high - low +1; // Длина массива
int frag = n; // Число упорядоченных фрагментов
int len = 1; // Длина сливаемых фрагментов
Key * source = array, // Массив, из которого происходит слияние
* dest = new Key[n]; // Массив, в который происходит слияние
int sourceLow = low, // Нижняя граница индексов массива-источника
destLow = 0; // Нижняя граница индексов массива-назначения
while (frag > 1) {
// Один шаг цикла слияния состоит в попарном слиянии фрагментов
// исходного массива и переносе оставшихся неслитыми элементов
// из исходного массива в результирующий.
// Индексы pSource и pDest задают нижние границы этих массивов,
int pSource = sourceLow, pDest = destLow;
do {
int nextSource =min(pSource + 2*len, sourceLow + n);
// Выполняем слияние двух фрагментов или
// перенос последнего оставшегося фрагмента
if (nextSource > pSource + len) {
merge<Key>(source, pSource, pSource+len-1, source, pSource+len, nextSource-1, dest, pDest);
} else {
move<Key>(source, pSource, nextSource-1, dest, pDest);
}
pSource = nextSource;
pDest += 2*len; }
while (pSource < sourceLow+n);
len*= 2; // Длина фрагментов увеличивается вдвое
frag = (frag+l)/2; // Число фрагментов уменьшается вдвое
// Переставляем местами массивы источника и назначения:
Key * tempArray = dest; dest =source; source = tempArray;
int tempLow = destLow; destLow = sourceLow; sourceLow = tempLow;
}
// Если в конце работы результат оказался не на месте,
//то организуется его перенос в исходный массив
if (source != array) {
move<Key>(source, sourceLow, sourceLow+n-1, dest, destLow);
}
}
Все темы данного раздела:
Оптимизация поиска в дереве
Основное свойство дерева соответствует пословице " дальше в лес - больше дров" . Точнее, количество просматриваемых вершин от уровня к уровню растет в геометрической прогр
Нумерация вершин
Способы обхода дерева.В деревьях обход вершин возможен только с использованием рекурсии, поэтому и их логическая нумерация производится согласно последовательности их рекурсивного о
Поиск и включение в двоичное дерево
Свойства двоичного дерева позволяют применить в нем алгоритм поиска, аналогичный двоичному поиску в массиве. Каждое сравнение искомого значения и значения в вершине позволяет выбрать для следующего ша
Сбалансированные двоичные деревья
После каждой операции изменения дерева можно проводить балансировку дерева, которая позволяет минимизировать его высоту. При этом поиск по двоичному дереву будет требовать минимальн
Преобразование лозы в сбалансированное двоичное дерево.
Этот этап алгоритма более содержательный и поэтому менее очевидный. Поэтому сначала будет разобран простой пример, а потом будет дано его обобщение.
Пусть есть лоза, котора
Алгоритмы представления графа
При программировании задач обработки сетевых структур требуется решить вопрос о представлении графа структурами данных языка программирования. Выбор представления графа определяется
Файл setgraph.h
#include "graph.h"
#include "set.h" // Определение класса для работы с множествами
class SetGraph : public Graph {
Set **graph; // Массив множеств дуг
Представление графа в виде матрицы смежности
Еще один распространенный способ представления графа — это представление в виде матрицы смежности размером N * N (рис.1). B этой матрице в элементе с индексами (i,j) записывается ин
Файл MatrixGraph.cpp
#include "MatrixGraph.h"
// Реализация конструктора - заказ и инициализация памяти
// под двумерный массив логических значений
MatrixGraph::Matr
Представление графа в виде связанного списка
Списки вообще удобны тем, что могут содержать переменное количество элементов, при этом общий размер занимаемой ими памяти соответствует количеству элементов списка. Каждый элемент списка будет сод
Файл ListGraph.h
#include "graph.h" // Описание родительского класса
// Описание шаблона классов для представления
// простых однонаправленных списков
template &
Файл ListGraph.cpp
#include "ListGraph.h"
// Реализация операций над списком.
// Добавление нового элемента в список
template <class T>
void List<
Представление графа в виде списка дуг
Иногда используются и другие представления графов, например, для случая очень разреженных графов, когда при большом количестве N вершин графа число дуг существенно меньше NXN, напри
Файл ArcGraph.h
#include "graph.h" // Определение родительского класса
// Описание класса для представления A-графа
class ArcGraph : public Graph {
// Дуга представлена элемент
Файл ArcGraph.cpp
«include "ArcGraph.h"
//Реализация операции добавления дуги
void ArcGraph::addArc(int from, int to) {
// Сначала проверяем правильность задания
Файл convert.срр
#include "SetGraph.h"
#include "MatrixGraph.h"
#include "ListGraph.h"
#include "ArcGraph.h"
// Функция пр
Обходы в графах
Как и в случае обхода деревьев, для графов существуют два основных класса обходов: обходы в глубину и обходы в ширину.
Обходы в глубину пытаются каждый раз
Определение путей и контуров Эйлера
Путь Эйлера проходит по каждому ребру в графе только один раз. Контур Эйлера проходит каждое ребро в графе тоже один раз, а также начинается и заканчивается в одной и той же вершине
Поиск кратчайших путей
Путем в графе называют чередующуюся последовательность вершин и дуг v1, e1, v2, e2,... vn-1 en-1, vn, в которой каждый элемент vi— вершина графа, а каждый элемент еi — дуга графа, ведущая из пре
Алгоритм Э. Дейкстры.
Опишем алгоритм нахождения такого пути при условии, что длины всех дуг неотрицательны. Этот алгоритм был предложен и опубликован Э. Дейкстрой (Е. W. Dijkstra), поэтому и носит его имя.
Алг
Алгоритм Флойда — Уоршалла
Идея алгоритмом Флойда — Уоршалла, состоит в следующем. Будем рассматривать последовательность матриц смежности. В этой матрице элемент с индексами (i,j) равен +∞, если в графе нет ребра, вед
Определение остовных деревьев
Остовиым деревом (скелетом) неориентированного графа называется его подграф, не имеющий циклов и содержащий все вершины исходного графа. Так, например, для нагруженного графа, изображенно
Файл listgraph.h
// Класс ListGraph задает структуру L-графа
class ListGraph {
// Массив списков дуг
List<int> *graph;
// Количество вершин графа
i
Файл Arc.h
// Структура ребра для алгоритма Крускала: сравнение ребер
// происходит по их весам
struct Arc {
int from, to;
double weight;
Arc(int f
Файл listgraph.cpp
// Собственно алгоритм Крускала
double ListGraph::minSkeleton(
// Выходной поток для вывода результирующей информации:
std::ostream & out,
// Нагрузка на реб
Сортировка выбором
Один из самых простых алгоритмов сортировки работает следующим образом. Сначала отыскивается наименьший элемент массива, затем он меняется местами с элементом, стоящим первым в сорт
Сортировка вставками
Метод сортировки заключается в том, что отдельно анализируется каждый конкретный элемент, который затем помещается в надлежащее место среди других, уже отсортированных элементов. Сл
Пузырьковая сортировка
Метод сортировки, который многие обычно осваивают раньше других из-за его исключительной простоты, называется пузырьковой сортировкой (bubble sort), в рамках которой выполняются сле
Быстрая сортировка
Алгоритм быстрой сортировки обладает привлекательными особенностями: он принадлежит к категории обменных (in-place) сортировок (т.е., требует всего лишь небольшого вспомогательного
Пирамидальная сортировка
Итак, мы постепенно переходим от более-менее простых к сложным, но эффективным методам.
В качестве некоторой прелюдии к основному методу, рассмотрим перевернутую сортировку
Двоичный поиск
Если данные отсортированы, то может использоваться очень хороший метод поиска, названный двоичным поиском. При таком поиске используется метод "разделяй и властвуй". Сначала производится
Работа со словарем. Иоиск и вставка. Хеширование.
Довольно часто встречаются ситуации, когда обработке подлежат много маленьких строк — слов, которые надо сохранять в некоторой единой структуре — словаре. Сами слова н
Файл dictionary.h
// Класс, представляющий словарь в виде хеш-таблицы
classHashDictionary
{
private:
static const intP = 557;
Файл dictionary.cpp
// Реализация функций
intHashDictionary::code(char c)
{
returnstrchr("abcdefghijklmnopqrstuvwxyz&
Файл "hashtable.h".
// Класс, представляющий хеш-таблицу пар (ключ, значение), причем
// ключом является строка, а значением может быть произвольный объект.
//В таблице хранятся не са
Алгоритм прямого поиска подстроки в строке
1. Установить i на начало строки S, т.е. i = 0.
2. Проверить, не вышло ли i + M за границу N строки S. Если да, то алгоритм
Новости и инфо для студентов