Министерство образования и науки Российской Федерации
НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ
Кафедра прикладной математики
Лабораторная работа №4
по дисциплине «Методы построения и анализа алгоритмов»
На тему " Деревья"
Факультет: ПМИ
Группа: ПМИ-21
Студент: Давыдов Д.В.
Преподаватель: Щукин Г.А.
Новосибирск
2013
1. Задание.
1. Пирамидальная сортировка. Реализовать пирамидальную сортировку. Провести
тест для массива строк, сравнить с другими сортировками (время выполнения, число обменов и сравнений).
2. БДП
Получить полный список файлов для некоторого каталога и всех его подкаталогов (например, со своего компьютера). Для имени и размера файла (ключи) построить бинарное дерево поиска и найти:
высоту и кол-во узлов получившегося дерева
время на построение дерева
мин. и макс. элементы (+ имена соотв. файлов)
время поиска произвольных элементов в дереве
(средний и худший варианты; сравнить со временем обычного поиска в исходном списке)
время на сортировку
3. Реализовать сбалансированное дерево поиска ( 2-3 дерево). Провести тесты из предыдущего пункта и сравнить результаты.
2. Пирамидальная сортировка.
Сначала строим дерево (пирамиду) с учетом того ,что самый наибольший элемент из множества(/наименьший) будет находится в корне дерева. После меняем последний элемент с корнем, и строим заново пирамиду, но уже из множества, в котором нет последнего элемента. И так повторяем, пока не отсортируем весь массив.
Оценка сложности. Максимальный/минимальный элемент из неотсортированного множества выбирается за O(log n). Тогда общее быстродействие сортировки будет
n* O(log n)= O(n log n).
Реализация.
построение пирамиды.
void siftDown(int i, int j)
{
bool done = false;
int maxChild;
char temp[mx];
while ((i * 2 < j) && (!done))
{
if (i * 2 == j)
maxChild = i * 2;
else
if (strcmp(A[i*2],A[i*2+1])>0)
maxChild = i * 2;
else
maxChild = i * 2 + 1;
if (strcmp(A[i],A[maxChild])<0)
{
strcpy(temp,A[i]);
strcpy(A[i],A[maxChild]);
strcpy(A[maxChild],temp);
i = maxChild;
change++;
}
else
{
done = true;
}
comparison++;
}
}
void HeapSort()
{
int size=input()-1;
int i;
char tmp[mx];
for (i = (size / 2) - 1; i >= 0; i--)
{
siftDown(i,size);
}
for (i = size - 1; i >= 1; i--)
{
strcpy(tmp,A[0]);
strcpy(A[0],A[i]);
strcpy(A[i],tmp);
change++;
siftDown(0,i-1);
}
}
Тестирование и сравнение результатов.
|
Тип сортировки |
Количество элементов |
Время |
Количество сравнений |
Количество обменов |
|
Выбором |
10000 |
2,69 |
499995000 |
9999 |
|
Вставками |
0,69 |
25259604 |
9999 | |
|
Слияние |
0,008 |
123579 |
272640 | |
|
Быстрая |
0,0012 |
74102 |
34368 | |
|
Пирамидальная |
0,22 |
127204 |
134681 | |
|
Выбором |
50000 |
13,75 |
124997500 |
49999 |
|
Вставками |
3,78 |
623959503 |
49996 | |
|
Слиянием |
0,06 |
783375 |
1692492 | |
|
Быстрая |
0,05 |
426650 |
200466 | |
|
Пирамидальная |
0,828 |
746638 |
750815 | |
|
Слияние |
100000 |
0,11 |
1566529 |
3386932 |
|
Быстрая |
0,10 |
1201173 |
438498 | |
|
Пирамидальная |
1,6680 |
1609487 |
1674410 | |
|
Слияние |
1000000 |
1,244 |
18716141 |
3995088 |
|
Быстрая |
0,792 |
151103975 |
5270956 | |
|
Пирамидальная |
17,3510 |
19396662 |
20048722 |