алгоритмы сортировки ответы на вопросы vkclub152685050

Сортировка Расческой

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

,

где – экспонента, а – «золотое» число.

Беря ϕ в расчет, можно получить оптимальное стартовое m=n/ϕ с округлением до ближайшего целого, n – размер сортируемого массива.

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

существует элемента для				сравнения,		расположенного			на	позиции m+1
(Выход за границы массива).
	Итерации	Элементы
	Начало	5		7	9		1		3		8
	1, m=4, k=2	5		7	9		1		3		8
	2, m=3, k=3	3		7	9		1		5		8
	3, m=2, k=4	1		5	8		3		7		9
	4, m=1, k=5	1		3	7		5		8		9
	5, m=0, k=6 Конец	1		3	5		7		8		9

Демонстрация итеративной работы алгоритма. k - количество сравнений за итерацию, m – расстояние между двумя сравниваемыми элементами в позициях. Пример работы 3й итерации приведен ниже. Выделенные области – позиции сравниваемых элементов

Обход		Элементы
Начало k=0	3			7			9		1			5			8
3, m=3, k++		1		7			9			3		5			8
3, m=3, k++	1				5		9		1				7		8
2, m=3, k=3. Конец	3			7			8		1			5			9

5

Алгоритм имеет следующие сложности:

Худшее время:	O(n2)
Лучшее время:	O(n)
Среднее время:	O(n2/2p), где p – число приращения
Затраты памяти:	O(n)

1.6 Пример выполнения работы

Предположим, что необходимо выполнить следующий вариант задания:

	№	Задание	Алгоритм сортировки
	вар.
	29	Найти k-ое по порядку число среди элементов массива	Пузырьком

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

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

uint16_t mas[]={ 5, 7, 9, 1, 3, 8 }; uint16_t tmp = 0;

uint16_t numOfReshuffle = 0; uint16_t numOfCompare = 0; bool needtosort = false;

for (uint16_t i = 0; i < sizeof(mas) / sizeof(uint16_t); i++)

{

for(uint16_t j=0; j < sizeof(mas) / sizeof(uint16_t) - i; j++) if (mas[j] > mas[j + 1])

{

numOfCompare++; tmp = mas[j+1];

6

mas[j + 1] = mas[j]; mas[j] = tmp; numOfReshuffle++; needtosort = true;

}

else

{

numOfCompare++;

}

if (!needtosort) break;

needtosort = false;

}

delete[] mas;

Теперь подсчитываем теоретические сложности алгоритма. Разработанный алгоритм использует следующие данные:

один массив размерностью n = sizeof(mas) / sizeof(uint16_t);

две переменные целого типа и одну логическую переменную.

Значит, пространственная сложность алгоритма определяется следующим образом:

v = + n*Cuint16_t + 2*Cuint16_t + Cbool

где Cuint16_t – константа, характеризующая объем памяти, отводимый под переменную беззнакового 16-тиразрядного целого типа.

Теоретическая пространственная сложность алгоритма составляет:

V(n) = O(v) = O(max(O(n*Cuint16_t), O(2*Cuint16_t), O(Cbool))) =

O(max(O(n), O(1), O(1))) = O(n)

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

TSort = O(max(O(K1), O( *K2))) = O(max(O(1), O( ))) = O( ),

Где K1 – операции сравнения, присваивания, используемые в алгоритме и имеющие временную сложность «1», K2 – цикличные операции, занимающие в наихудшем случае шагов.

7

1.7Контрольные вопросы

1)Что такое сортировка?

2)Какие существуют виды сортировки, определяемые местоположением сортируемых данных? Какие особенности каждого из этих видов?

3)Какова временная и пространственная сложность алгоритмов внутренней сортировки?

4)Почему теоретическая оценка быстродействия алгоритма быстрой сортировки носит вероятностный характер?

5)В чем отличительная особенность алгоритма сортировки распределением и в чем основной недостаток вырожденной сортировки распределением?

6)Что такое временная и пространственная сложность алгоритма?

7)Что такое теоретическая временная и теоретическая пространственная сложность алгоритма?

8