Лабораторные работы №№1-5 по дисциплине: Структуры и алгоритмы обработки данных. Вариант №7

Лабораторная работа №1
1. Разработать процедуры сортировки массива целых чисел методом прямого выбора, методом пузырьковой сортировки и методом шейкерной сортировки (язык программирования Паскаль или Си).
2. Правильность сортировки проверить путем подсчета контрольной суммы и числа серий в массиве.
3. Во время сортировки предусмотреть подсчет количества пересылок и сравнений (М и С), сравнить их с теоретическими оценками.
4. Составить таблицу следующего вида (данные получить экспериментально) для n= 100, 200, 300, 400, 500. (n – количество элементов в массиве)
Метод N количество элементов в массиве С для упорядоченного массива М для упорядоченного массива С для случайного массива М для случайного массива Время сортировки при N=5000
Прямой выбор 100 4950 297 4950 297 0.000000….
200 19900 597 19900 597
300 44850 897 44850 897
400 7980 1197 7980 1197
500 124750 1497 124750 1497
Пузырьковая 100 4950 0 4950 7143 1.540000…
200 19900 0 19900 29127
300 44850 0 44850 64989
400 79800 0 79800 119892
500 124750 0 124750 185673
Шейкерная 100 99 0 3501 7601 1.270000…
200 199 0 13409 29346
300 299 0 31991 70440
400 399 0 51258 112353
500 499 0 83356 187617
5. Проанализировать полученные результаты. Какой из методов самый быстрый? Самый медленный? Как сложность зависит от начальной отсортированности?

Лабораторная работа №2
1. Разработать процедуры сортировки массива целых чисел методом Шелла, методом пирамидальной сортировки и методом Хоара (язык программирования Паскаль или Си).
2. Правильность сортировки проверить путем подсчета контрольной суммы и числа серий в массиве.
3. Во время сортировки предусмотреть подсчет количества пересылок и сравнений (М и С), сравнить их с теоретическими оценками.
4. Составить таблицу следующего вида (данные получить экспериментально) для n= 100, 200, 300, 400, 500. (n – количество элементов в массиве)
Метод N количество элементов в массиве С для упорядоченного массива М для упорядоченного массива С для случайного массива М для случайного массива
Метод Шелла 100 629 1211 649 1231
200 1994 3174 2096 3276
300 4402 6182 4572 6352
400 8790 11168 8288 10666
500 12493 15471 13321 16299
Пирамидальная сортировка 100 1434 1073 1473 1086
200 3501 2362 3489 2358
300 5712 3699 5775 3720
400 8139 5108 8193 5126
500 10623 6536 10485 6490
Метод Хоара 100 1460 1213 1202 898
200 2453 1899 2299 1992
300 3220 2534 3026 2146
400 5557 5110 5465 4923
500 6412 5317 6894 6278
5. Проанализировать полученные результаты. Какой из методов самый быстрый? Самый медленный? Как сложность зависит от начальной отсортированности?
Сравните трудоемкости методов быстрой сортировки и трудоемкости методов с квадратичной трудоемкости (использовать результаты лабораторной работы №1)

Лабораторная работа №3
Порядок выполнения работы:
1. Разработать процедуры сортировки последовательности целых чисел методом прямого слияния и методом цифровой сортировки (язык программирования Паскаль или Си).
2. Во время сортировки предусмотреть подсчет количества пересылок элементов в очередь и сравнений (М и С), сравнить их с теоретическими оценками.
3. Составить таблицу следующего вида (данные получить экспериментально) для n= 100, 200, 300, 400, 500. (n – количество элементов в массиве)
Метод N количество элементов в массиве С для упорядоченного массива М для упорядоченного массива С для случайного массива М для случайного массива
Слияние 100 667 767 723 823
200 1532 1732 1647 1847
300 2472 2772 2646 2946
400 3460 3860 3693 4093
500 4486 4986 4777 5277
Цифровая сортировка 100 2970 372 2970 372
200 5684 558 5684 558
300 9108 530 9108 730
400 11484 930 11484 930
500 15147 1104 15147 1104
4. Проанализировать полученные результаты. (Какой из методов самый быстрый? Самый медленный? Как сложность зависит от начальной отсортированности?)

Лабораторная работа №4
Написать программу «Телефонный справочник», которая обрабатывает данные об абонентах телефонной станции. Каждый абонент имеет имя, адрес, телефонный номер. В программе описать массив абонентов (назовем его справочник). В справочнике должно быть не менее 20 элементов, которые заполняются либо программно, либо считываются из файла.
С помощью индексов и фильтров выбрать абонентов, которые имеют имя и адрес в заданном диапазоне.
Результаты работы программы:
1. Пункты главного меню.
2. Вывод базы данных на экран:
3. Ввод верхней и нижней границ поиска:
4. Результаты поиска по имени:
5. Результаты поиска по адресу

Лабораторная работа №5
1. Построить хэш-таблицу методом линейных проб для слов заданного текста. Текст находится в некотором файле (примерно 200 слов). Экспериментально определить минимально необходимый объем хэш-таблицы и число коллизий при построении.
2. Построить хэш-таблицу методом квадратичных проб для слов заданного текста. Файл с текстом должен быть тот же, что и п.1. Экспериментально определить минимально необходимый объем хэш-таблицы и число коллизий при построении.
3. Заполнить следующую таблицу полученными данными. Проанализировать результаты. (Какой метод требует большего объема памяти? Для какого из методов меньшее число коллизий?).

Все работы успешно зачтены!
В архиве отчеты по лабораторным работам + программа к каждой работе (выполнены в Pascal).