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

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)

Зачет!
В архиве отчет + программа.