Вопрос 6. Пирамидальная сортировка.

Пирамидальная сортировка — алгоритм сортировки, работающий в худшем, в среднем и в лучшем случае (то есть гарантированно) за Θ(n log n) операций при сортировке n элементов. Количество применяемой служебной памяти не зависит от размера массива (то есть, O(1)).

Может рассматриваться как усовершенствованная сортировка пузырьком, в которой элемент всплывает (min-heap) / тонет (max-heap) по многим путям.

Необходимо отсортировать массив AA, размером nn. Построим на базе этого массива за O(n)O(n) кучу для максимума. Так как максимальный элемент находится в корне, то,если поменять его местами с A[n−1]A[n−1], он встанет на свое место. Далее вызовем процедуру siftDown(0)siftDown(0), предварительно уменьшив heapSizeheapSize на 11. Она за O(logn) просеет A[0]A[0] на нужное место и сформирует новую кучу (так как мы уменьшили ее размер, то куча располагается с A[0]A[0] по A[n−2]A[n−2], а элемент A[n−1]A[n−1]находится на своем месте). Повторим эту процедуру для новой кучи, только корень будет менять местами не с A[n−1]A[n−1], а с A[n−2]A[n−2]. Делая аналогичные действия, пока heapSizeheapSize не станет равен 11, мы будем ставить наибольшее из оставшихся чисел в конец не отсортированной части. Очевидно, что таким образом, мы получим отсортированный массив.

Вопрос 7.Быстрая сортировка.

Быстрая сортировка:

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

void SortAlgo::quickSort(int* data, int const len)

{

int const lenD = len;

int pivot = 0;

int ind = lenD/2;

int i,j = 0,k = 0;

if(lenD>1){

int* L = new int[lenD];

int* R = new int[lenD];

pivot = data[ind];

for(i=0;i<lenD;i++){

if(i!=ind){

if(data[i]<pivot){

L[j] = data[i];

j++;

}

else{

R[k] = data[i];

k++;

}

}

}

quickSort(L,j);

quickSort(R,k);

for(int cnt=0;cnt<lenD;cnt++){

if(cnt<j){

data[cnt] = L[cnt];;

}

else if(cnt==j){

data[cnt] = pivot;

}

else{

data[cnt] = R[cnt-(j+1)];

}

}

}

}

Вопрос 8. Алгоритм Дейкстры.

Алгоритм Де́йкстры — алгоритм на графах, изобретённый нидерландским учёным Эдсгером Дейкстрой в1959 году. Находит кратчайшие пути от одной из вершин графа до всех остальных. Алгоритм работает только для графов без рёбер отрицательного веса. Алгоритм широко применяется в программировании и технологиях, например, его используют протоколы маршрутизации OSPF и IS-IS.

Вопрос 9.Шаблоны проектирование. Что? Зачем? Почему?

Паттерн проектирования — это часто встречающееся решение определённой проблемы при проектировании архитектуры программ.

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

Вы можете вполне успешно работать, не зная ни одного паттерна. Более того, вы могли уже не раз реализовать какой-то из паттернов, даже не подозревая об этом.

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

• Проверенные решения. Вы тратите меньше времени, используя готовые решения, вместо повторного изобретения велосипеда. До некоторых решений вы смогли бы додуматься и сами, но многие могут быть для вас открытием.

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

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

Классификация Паттернов

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

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

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

Кроме того, паттерны отличаются и предназначением. В данном пособии будут рассмотрены три основные группы паттернов:

• Порождающие паттерны беспокоятся о гибком создании объектов без внесения в программу лишних зависимостей.

• Структурные паттерны показывают различные способы построения связей между объектами.

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