Алгоритмы сортировки на языке программирования c#

Question

Алгоритмы сортировки на языке программирования c#

ZrOuw Знаток (269), на голосовании 7 месяцев назад

Вот полученное мною задание: Реализовать алгоритмы сортировки - (Выполнил). Определить порядок сложности этих алгоритмов относительно операций сравнения (Это имеется ввиду сложность в среднее время?
(пузырек : O(N^2)
быстра сортировка: O(N*log(N))
Шелла: -
вставками: O(N^2)
слиянием: O(N*log(N)) )?)
, а также коэффициенты пропорциональности: F(N) = C*N*log2(N). Для аппроксимации можно использовать метод наименьших квадратов и сервис «Поиск решения». (Ну предположим:
Пузырьковая сортировка:
N = 600000: F(600000) = C * 600000 * log2(600000)
N = 40000: F(40000) = C * 40000 * log2(40000)
N = 1400000: F(1400000) = C * 1400000 * log2(1400000)
N = 1600000: F(1600000) = C * 1600000 * log2(1600000)
N = 350000: F(350000) = C * 350000 * log2(350000) А что дальше? Я совсем не выкупил, что имеется ввиду в задании)

Результаты соберите в одну сравнительную таблицу. План проведения экспериментов с алгоритмами представьте в виде xml-файла. Например,
<experiments>
<experiment Length=”1000” Counts=”100”>
<\experiment>
………
<\experiments> (С этой частью надеюсь разберусь)

Вот мой входной массив - BigInteger[] arr = { 1000000000, 50000000, 750000, 300000, 80000, 2000000, 150000,
2500000000, 55000000, 350000, 600000, 90000, 1800000, 170000,
3500000000, 150000000, 90000, 700000, 40000, 1200000, 200000,
4500000000, 250000, 100000, 800000, 50000, 1400000, 250000,
5500000000, 350000000, 200000, 900000, 60000, 1600000, 300000,
6500000000, 45000000, 300000, 1000000, 70000, 2000000, 350000 };
А вот результаты времени выполнения сортировок:
Время выполнения сортировки 'Пузырёк': 00:00:00.0001933
Время выполнения быстрой сортировки: 00:00:00.0002459
Время выполнения сортировки 'Шелла': 00:00:00.0001474
Время выполнения сортировки 'Вставками': 00:00:00.0001867
Время выполнения сортировки 'Слиянием': 00:00:00.0005742
Помогите разобраться с тем, что от меня в принципе требуется в задании)

Answer 1

В данном задании вам предлагается провести анализ времени выполнения алгоритмов сортировки для различных размеров входных данных. Для этого вам нужно выполнить следующие шаги:

Реализация алгоритмов сортировки: Реализуйте алгоритмы сортировки (пузырьковую, быструю, сортировку Шелла, сортировку вставками и слиянием) на C#. Вы уже сделали это, так как у вас есть результаты времени выполнения этих алгоритмов для заданных входных данных.

Измерение времени выполнения: Используйте ваши реализации алгоритмов сортировки для измерения времени выполнения для разных размеров входных данных. В вашем случае входные данные уже предоставлены в виде массива arr.

Аппроксимация времени выполнения: После того, как вы измерите время выполнения для различных размеров входных данных, вам нужно аппроксимировать полученные данные, чтобы определить коэффициенты пропорциональности для функции F(N) = CNlog2(N). Это можно сделать с помощью метода наименьших квадратов, который позволяет подобрать наилучшую прямую линию для полученных данных.

Определение порядка сложности: После того, как вы найдете коэффициенты пропорциональности для каждого алгоритма сортировки, вы можете определить порядок сложности каждого алгоритма относительно операций сравнения. Например, для алгоритма быстрой сортировки порядок сложности в среднем времени составляет O(N*log(N)).

Подготовка таблицы: Соберите результаты в одну сравнительную таблицу, где каждый столбец будет содержать информацию о времени выполнения и порядке сложности для каждого алгоритма сортировки.

Подготовка плана экспериментов: Составьте план проведения экспериментов в виде XML-файла. Этот план должен содержать информацию о длине входных данных и количестве повторений эксперимента для каждого размера входных данных.