ОЦЕНКА ЭФФЕКТИВНОСТИ АЛГОРИТМОВ (С++)

Написать две программы согласно номеру индивидуального варианта. В первой программе провести сравнение указанных алгоритмов сортировки массивов, содержащих N1, N2, N3 и N4 элементов. Каждую функцию сортировки вызывать трижды: для сортировки неупорядоченного массива, упорядоченного массива и массива, упорядоченного в обратном порядке. При работе каждого алгоритма сортировки выполнить подсчет основных (производимых над элементами массива) и вспомогательных (всех остальных) операций, указанных в вариативной части задания (сравнений или присваиваний), а также зафиксировать время работы алгоритма. Сортируемая последовательность для всех методов должна быть одинаковой (считывать необходимое количество элементов из прилагаемого файла test_numbers.txt). Оценить время работы и эффективность алгоритмов сортировки по заданному критерию и объему требуемой дополнительно памяти.

При выполнении задания на повышенном уровне сложности дополнительно провести анализ того, как наличие повторяющихся ключей во входной последовательности влияет на трудоемкость каждого из рассматриваемых алгоритмов сортировки. Для этого создать четыре файла, содержащих N4 неупорядоченных чисел, в которых значения элементов будут повторяться по 10, 100, 500 и 1000 раз, и так же, как в первой половине работы, выполнить сортировку этих последовательностей (неупорядоченных, упорядоченных и упорядоченных в обратном порядке) каждым из методов.

Во второй программе реализовать две указанные структуры данных, заполнив их значениями из приложенного файла test_numbers.txt. Выполнить поиск 100 ключей в указанных структурах данных, для каждого ключа выводить сообщение о том, найден он или нет, и количество выполненных при поиске сравнений ключей, в конце программы вывести среднее количество сравнений, пришедшееся на один ключ. При формировании тестового набора включать в него как имеющиеся в файле, так и отсутствующие в нем ключи (меньшие 10000000, большие 100000000 и принадлежащие интервалу [10000000; 100000000) ). Оценить количество требуемой памяти для реализации каждой структуры и количество сравнений при поиске.

1. Порядок: по убыванию элементов. Методы: выбора, простых вставок, Шелла (шаг сортировки hk-1=3hk+1, ht=1, t=log3n-1), сортировка прямым слиянием. N1=10000, N2=18000, N3=30000, N4=60000. Критерий – количество сравнений. 2. Декартово дерево, бор. Подсчет выделяемой памяти произвести в программе