38. Алгоритмы сортировки. Сортировка распределением. Сравнение алгоритмов внутренней сортировки.

Сортировка распределением интересна тем, что она сортирует массив, не сравнивая элементы друг с другом.

При вырожденном распределении предполагается, что каждый элемент массива может принимать m (например, от 1 до m) фиксированных значений. Заведем массив Amount размерностью m, первоначально обнулив его. Затем для каждого i подсчитаем количество элементов массива A, равных i, и занесем это число в Amount[i]. После чего, в первые Amount[1] элементов массива A запишем 1, в следующие Amount[2] элементов массива A запишем 2 и т. д. до тех пор, пока не дойдем до конца массива A (заметим, что в то же время мы окажемся в конце массива Amount).

Недостатком этого метода является то, что требуется дополнительная память размером порядка m, а это может оказаться недопустимым из-за большого значения m. Но, если m>>n, то имеется способ уменьшить объем требуемой дополнительной памяти, который сейчас и рассмотрим, как общий случай сортировки распределением.

Сравнение алгоритмов внутренней сортировки

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

Существует таблица которая показывает методы сортировки их теоретические, временные и пространственные сложности.

Эта таблица позволяет сделать ряд выводов.

1. На небольших наборах данных целесообразнее использовать сортировку включением, так как этот на практике оказывается самым быстрым. Еще одно преимущество, что он использует полную или частичную упорядоченность входных данных и на упорядоченных данных работает быстрее.

2. Алгоритм пузырьковой сортировки, причем в той его модификации, которая не использует частичный порядок данных исходного массива.

3. Сортировка Шелла оказывается лишь красивым теоретическим методом, потому что на практике использовать его нецелесообразно: он сложен в реализации, но не дает такой скорости, какую дают сравнимые с ним по сложности программной реализации методы.

4. При сортировке больших массивов исходных данных лучше использовать быструю сортировку.

5. Сортировка слиянием работает быстрее, но следует помнить, что она требует дополнительную память размером порядка n.

6. В тех же случаях, когда есть возможность использовать дополнительную память размером порядка n, имеет смысл воспользоваться сортировкой распределением.

39. Алгоритмы обхода графа. Поиск в глубину.

При решении многих задач, касающихся графов, необходимы эффективные методы систематического обхода вершин и ребер графов. К таким методам относятся:

– поиск в глубину;

– поиск в ширину.

Поиск в глубину

Поиск в глубину является обобщением метода обхода дерева в прямом порядке.

Метод обхода вершин орграфа называется поиском в глубину, поскольку поиск непосещенных вершин идет в направлении вперед (вглубь) до тех пор, пока это возможно. Если вершина y уже посещалась, то ищется другая вершина, смежная с вершиной x. Если вершина y ранее не посещалась, то она помечается как посещенная и поиск начинается заново от вершины y. Пройдя все пути, которые начинаются в вершине y, возвращаемся в вершину x, т. е. в ту вершину, из которой впервые была достигнута вершина y. Затем продолжается выбор нерассмотренных дуг, исходящих из вершины x, и так до тех пор, пока не будут исчерпаны все эти дуги.

Для представления вершин, смежных с вершиной v, можно использовать список смежных, а для определения вершин, которые ранее посещались, – массив Visited:

Graph: TAdjacencyList;

Visited: array[1..n] of boolean;

Чтобы применить эту процедуру к графу, состоящему из n вершин, надо сначала присвоить всем элементам массива Visited значение false, затем начать поиск в глубину для каждой вершины, помеченной как false.

Поиск в глубину для полного обхода графа с n вершинами и m дугами требует общего времени порядка O(max(n, m)). Поскольку обычно m ≥ n, то получается O(m).