Материал: Вопросы к экзамену

for (int j = input.length - 1; j > i; j--) { if (input[j] < input[j - 1]) {

swap(j, j-1);

}

}

}

25.Сортировка сравнениями. Сортировка вставками (insertion).

См. вопрос 24 +

Сортировка вставками (insertion):

Сортировка вставками (англ. Insertion sort) — алгоритм сортировки, в котором элементы

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

Псевдокод алгоритма:

for j = 2 to A.length do key = A[j]

i = j - 1

while (i > 0 and A[i] > key) do A[i + 1] = A[i]

i = i - 1 end while A[i+1] = key

end for

26.Сортировка сравнениями. Селекционная сортировка (selection).

См. вопрос 24 +

Сортировка выбором (selection).

Сортировка выбором (Selection sort) — алгоритм сортировки( 2).. На массиве из элементов имеет время выполнения в худшем, среднем и лучшем случае , предполагая что сравнения делаются за постоянное время.

Aлгоритм:

3. находим номер минимального значения в текущем списке

21

4.производим обмен этого значения со значением первой неотсортированной позиции (обмен не нужен, если минимальный элемент уже находится на данной позиции)

5.теперь сортируем хвост списка, исключив из рассмотрения уже отсортированные элементы

(T – тип данных)

void selection_sort(T array[], unsigned int size) {

for (unsigned int idx_i = 0; idx_i < size - 1; idx_i++) { unsigned int min_idx = idx_i;

for (unsigned int idx_j = idx_i + 1; idx_j < size; idx_j++) { if (array[idx_j] < array[min_idx]) {

min_idx = idx_j;

}

}

if (min_idx != idx_i) { swap(array[idx_i], array[min_idx]); min_idx = idx_i;

}

}

}

27.Сортировка «разделяй и властвуй». Сортировка слияниями (merge-sort).

Принцип «разделяй и властвуй» (divide and conquer) – парадигма разработки алгоритмов,

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

Алгоритм сортировки слиянием это типичный пример принципа «разделяй и властвуй». Чтобы отсортировать массив чисел по возрастанию, он разбивается на две равные части, каждая сортируется, затем отсортированные части сливаются в одну. Эта процедура применяется к

размер исходного массива.

28.Сортировка «разделяй и властвуй». Быстрая сортировка (quick-sort).

См. вопрос 27 +

QuickSort является существенно улучшенным вариантом алгоритма сортировки с помощью прямого обмена («Пузырьковая сортировка»). В первую очередь производятся перестановки на наибольшем возможном расстоянии и после каждого прохода элементы делятся на две независимые группы.

Общая идея алгоритма состоит в следующем:

22

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

•Сравнить все остальные элементы с опорным и переставить их в массиве так, чтобы разбить массив на два непрерывных отрезка, следующих друг за другом: «элементы меньшие

опорного» и «равные или большие».

• Для обоих отрезков значений выполнить рекурсивно ту же последовательность операций, если длина отрезка больше единицы.

void quicksort(A, low, high) { if (low <= high) {

p := partition(A, low, high) quicksort(A, low, p - 1) quicksort(A, p + 1, high)

}

}

29.Сортировка с использованием деревьев. Пирамидальная сортировка (heap-sort).

Двоиичная куча, пирамиида, или сортирующее дерево — такое двоичное дерево, для

которого выполнены три условия:

•Значение в любой вершине не меньше, чем значения её потомков.

•Глубина всех листьев (расстояние до корня) отличается не более чем на 1 слой.

•Последний слой заполняется слева направо без «дырок».

Высота кучи определяется как высота двоичного дерева. То есть она равна количеству рёбер в самом( длинномlog ) простом пути, соединяющем корень кучи с одним из её листьев. Высота кучи есть , где — количество узлов дерева.

Пирамидальная сортировка:

Удобная структура данных для сортирующего дерева — это такой массив Array, что

Array[0] — элемент в корне, а потомки элемента Array[i] являются Array[2i+1] и Array[2i+2].

Алгоритм сортировки будет состоять из двух основных шагов:

Процесс продолжается до тех пор, пока в сортирующем дереве не останется один элемент. Тогда упорядоченная последовательность.

Этот шаг требует ( log ) операций.

Пирамида – бинарное дерево, в узлах ключи сортируем по значениям данных. - Неубывающая; -Невозрастающая;

Метод простого выбора. N(n-1) сравнений, n-1 перестановок. Пирамидальная сортировка (сложность nlogn, неустойчивый алгоритм).

Дерево называется пирамидально упорядоченным, еслиключвкаждом его узле ≥ ключам всех его потомков. Сортирующее дерево – совокупность ключей, образующих полное пирамидально упорядоченное дерево. Для реализации дерева используется массив([i/2]- родитель, 2i, 2i+1- потомки). При такой организации прохождение по дереву проходит более быстро с большой экономией памяти. Поддержание основного свойства пирамид дерева.

Heapify(A[1..n],i)

1.L←2*i

2.R←2*i+1

3.If (L<=Head_size) and (A[L]>A[i])

4.Then largest←L

5.Else largest←i

6.If (R<=Head_size) and (A[k]>A[largest])

7.Then largest←R

8.If largest≠I then A[i]A[largest]

9.Hepify(A,largest)

Построение пирамиды

BiuldHeap(A[1..n])

1.Heap_size←n

2.For i=└n/2┘ downto 1 do

3.Heapify(a,i)

4.End for

5.

Сортировка

HeapSort(A[1..n])

1.BuildHeap(a)

2.For I = n downto 2 do

3.A[i]↔A[1]

4.Heapsize←Heapsize-1

5.Heapity(A,1)

6.End for

30.Сортировка больших файлов. Прямой алгоритм сортировки.

Подопределением''большиефайлы''понимаемданные,расположенныенапериферийных

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

24

Сортировка прямым слиянием:

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

31.Сортировка больших файлов. Естественный алгоритм сортировки.

См. вопрос 30 +

Естественное слияние последовательностей:

Алгоритм слияния можно использоватьи длясортировки массивов, если последовательно применить его несколько раз ко все более длинным упорядоченным последовательностям. Для этого:

1.висходномнаборевыделяютсядвеподрядидущиевозрастающиеподпоследовательности (серии)

2.эти подпоследовательности (серии) сливаются в одну более длинную упорядоченную последовательность так, как описано выше

3.шаги 1 и 2 повторяются до тех пор, пока не будет достигнут конец входного набора

4.шаги 1 –3 применяются к новому полученному набору, т.е. выделяются пары серий, которые сливаютсяв ещеболеедлинные наборы,и.т.д.до тех пор,пока небудет получена единая упорядоченная последовательность.

32.Графы. Основные понятия. Поиск в ширину. Поиск в глубину.

Граф, или неориентированный граф G — это упорядоченная пара G:=(V,E), где V—

непустое множество вершин или узлов, а E — множество пар (в случае неориентированного графа — неупорядоченных) вершин, называемых рёбрами.

графа и поиск закончится.

Поиск в ширину в графе. Не рекурсивный алгоритм.

Этот метод основан на замене стека очередью. В этом случае, чем раньше посещается вершина (помещается в очередь), тем раньше она используется (удаляется из очереди).

25