Курс лекций (стр. 13 из 24)

Граф – структура, состоящая из узлов и дуг, причем каждая дуга направлена от одного узла к другому.

Дерево – направленный граф, у которого только корневой узел не имеет дуг, входящих в него, в каждый узел входит не более одной дуги, в каждый узел можно попасть из корневого за несколько шагов.

Важное место при работе с агрегативными переменными занимают такие действия как поиск и сортировка данных. Рассмотрим основные методы таких действий.

ПОИСК

Поиск – это процесс нахождения нужных значений в некотором наборе данных.

Будем считать, что элемент данных - это запись (структура), состоящая из ключа (целое положительное число) и тела, содержащего некоторую информацию. Задача состоит в том, чтобы обнаружить запись с нужным ключом. Тело не влияет на поиск. Для простоты рассмотрим поиск в одномерном массиве.

1. Линейный поиск.

Наиболее простой в реализации, хотя его выполнение занимает наибольшее время. Элементы проверяются последовательно, по одному, до тех пор, пока нужный элемент не будет найден. Если массив содержит N элементов, то каждый раз, в среднем, будет проверяться N/2 элементов. Легко программируется, подходит для коротких массивов.

2. Двоичный поиск.

Для ведения двоичного поиска ключи должны быть упорядочены по величине или алфавиту. Если такое упорядочивание произведено заранее, то среднее максимальное время поиска в массиве с N элементами будет log₂N.

При двоичном поиске ключ (поиска) сравнивается с ключом среднего элемента в массиве. Если значение ключа больше, то та же самая операция повторяется для второй половины массива, если меньше - то для первой. Т.о. за каждый шаг объем поиска сокращается наполовину.

СОРТИРОВКА

Сортировкой (или упорядочением) называется переразмещение элементов данных в возрастающем или убывающем порядке. Существует большое количество методов сортировки, но ни один из них не является лучшим во всех отношениях.

При выборе метода сортировки необходимо учитывать

- число сортируемых элементов (N);

- до какой степени элементы уже отсортированы.

В качестве основных критериев оценки метода сортировки используют количество необходимых операций сравнения С и объем используемой памяти S. Количество сравнений С(N) для различных методов может быть от N² до N log₂N. Эффективность использования памяти определяется соотношением

где S(N) - объем памяти, занимаемый элементами данных до сортировки, DS(N) - объем дополнительной памяти, требуемой в процессе сортировки.

Задача сортировки состоит в том, чтобы расположить записи в порядке убывания (возрастания) ключей. Тело не влияет на сортировку. Для простоты рассмотрим сортировку одномерного массива.

1. Сортировка методом выборки

Из массива выбирается наименьший элемент и помещается в первый элемент массива, затем выбирается наименьший элемент из оставшихся и помещается во второй элемент массива. В качестве метода поиска наименьшего элемента может быть применен следующий ("Турнир с выбыванием"). На первом шаге сравниваем попарно элементы массива в следующем порядке А(1) с А(2), А(3) с А(4) и т.д. При этом наименьшие элементы массива помещаем на первое место, т.е. на А(1), А(3),…, а наибольшие - на второе. На втором шаге сравниваем первые элементы образовавшихся пар: А(1) с А(3), А(5) с А(7), … и наименьшие помещаем на первое место, т.е. в А(1), А(5),… По окончании процесса обнаружим наименьший элемент на месте первого элемента массива А(1). Далее метод поиска применим к части массива, начиная с А(2) и т.д.

Сортировка таким методом требует порядка N(N+1)/2 сравнений и практически не нуждается в дополнительной памяти.

2. Сортировка включением. Элементы выбираются по очереди и помещаются в нужное место. Один из возможных способов сортировки данным методом ("сортировка простым включением") таков. Начиная с первого элемента сравниваем последовательно пары соседних элементов и продвигаемся вперед до тех пор, пока выполняется условие А(К) <= А(К+1), К = 1,2,3,… Как только А(К) станет больше А(К+1) меняем их местами и начинаем возврат назад, последовательно проводя сравнение и обмен пар соседних элементов до тех пор, пока не будет нарушено условие А(L) > A(L-1), L = K,K-1,… Как только А(L) станет меньше или равно А(L-1), продолжаем процесс сравнения вперед, начиная с А(К+1) (при этом элементы А(1)…А(К+1) будут уже отсортированы). Процесс продвижения вперед, чередующийся с возвратом назад, продолжаем до К = N-1. Пример.

При сортировке простым включением требуется порядка N² сравнений, при этом практически не используется дополнительная память.

3. Сортировка распределением (метод корзин).

Среди методов сортировки распределением широкое распространение получила цифровая сортировка. Любой элемент массива рассматривается как совокупность цифр, а элементы сначала сортируются по значению старшей цифры, затем полученные подмножества (группы) сортируются по значению следующей цифры и т.д. Пусть каждый элемент массива А размером N представляет собой совокупность цифр С₁С₂С₃…С_m, где m - количество цифр максимального элемента (если какой-то элемент содержит меньше цифр, то он слева дополняется нулями). Последовательно просматривая элементы массива А, распределим их по группам: в первую группу объединим все элементы, у которых первая цифра - 0, во вторую - если первая цифра 1, в последнюю 10 - первая цифра 9. К каждой группе применим тот же метод, но относительно цифры С₂. Далее до цифры С_m. Пример.

Алгоритм цифровой сортировки не предполагает сравнение элементов и поэтому нельзя оценить ее эффективность обычным способом. Но если m (число цифр) мало, то ее показатели лучше, чем "N log₂N". Для цифровой сортировки требуется дополнительный массив размером N, и еще массив размером 10, в котором подсчитывается число элементов с выделяемой цифрой 0,1,…9.

4. Сортировка обменами.

Выбираются два элемента, и если друг по отношению к другу они не находятся нужном порядке, то меняются местами. Процесс продолжается пока никакие два элемента не нужно менять местами.

Метод "Быстрой сортировки". Устанавливаем I = 1, J = N. Сравниваем А(I) и А(J). Если А(I) <= А(J), то уменьшаем J на 1 и продолжаем сравнение. Последовательное уменьшение J и сравнение указанных элементов продолжаем пока не окажется, что А(I) > А(J). Тогда меняем местами эти элементы. После чего увеличиваем индекс I на 1 и снова сравниваем. Последовательное увеличение I и сравнение продолжаем до тех пор, пока не окажется, что А(I) > А(J). В этом случае меняем местами элементы и начинаем уменьшение J.

Чередуя увеличение I и уменьшение J приходим к некоторому элементу, который называется пороговым или главным, и характеризующемуся условием I = J (перед началом сортировки он находился в А(1)). Все элементы массива оказались разделенными главным элементом на две части так, что все элементы слева (сверху) меньше него, а справа (снизу) - больше. К этим двум массивам применяем тот же алгоритм и получаем четыре части и т.д.

Алгоритм "Быстрой сортировки" имеет максимальное число сравнений N², а минимальное N log₂N. Все зависит от выбора главного элемента (желательно, чтобы он делил массив на две равные части). Среднее число сравнений 2N log₂N. Дополнительная память используется для хранения стеков, в которые засылаются границы получаемых частей массивов.

5. Сортировка слиянием.

Два отдельно отсортированных массива затем срединяются в один массив таким образом, чтобы и он стал отсортированным. Пусть имеем два отсортированных массива В и С с числом элементов M и L. Процедура слияния в массив А с числом элементов N = M+L такова. В качестве А(1) выбираем наименьший из В(1) и С(1). Если это В(1), то в качестве А(2) - наименьший из В(2) и С(1) и т.д.

Чтобы применить такой метод к неотсортированному массиву, можно считать каждый его элемент сортированной последовательностью, состоящей из одного элемента. Объединяем каждую пару следующих подряд последовательностей в одну отсортированную последовательность. Затем объединяем по четыре элемента и т.д.

Этот метод требует N log₂N сравнений и один дополнительный массив, содержащий N элементов.

СТРАТЕГИИ РАСПРЕДЕЛЕНИЯ ПАМЯТИ.

Одним из типов задач поиска являются задачи распределения памяти, которые обычно возникают при создании операционных систем и во многих других случаях, связанных с использованием данных.

При распределении памяти (т.е. отведения под выполняемую программу, а затем освобождения) возникают свободные области. Эти области могут оказаться малы для размещения в них данных, и, следовательно, память становится фрагментарной (рис.13). Фрагментация памяти - это наличие большого числа несмежных участков свободной памяти очень маленького размера (фрагментов). Суммарный объем фрагментов может составить значительную величину, намного превышающую требуемый объем памяти для выбранной программы. Способы размещения вновь поступающих данных:

1. Первое возможное размещение.

Последовательно просматриваются области памяти, пока не будет найдена область, достаточная для размещения данных. Все свободные области организованы в список (рис.13). Найденная область изымается из списка, на ее место ставится меньшая свободная область - оставшаяся незанятой часть исключенной области. В рамках данного способа легко объединить две соседние области в одну, если они свободны (т.к. список областей упорядочен по адресам). Данный способ довольно прост, однако при его использовании сильно возрастает фрагментарность.