Исследование эффективности алгоритмов сортировок для различных структур и размерностей данных

Постановка задачи

• · Провести экспериментальный сравнительный анализ различных методов сортировки. Для чистоты эксперимента сортировка должна проводиться на одинаковых наборах входных данных, которые генерируются случайным образом. Для более полного анализа методов сортировка должна проводиться для различных размерностей данных, например: 500, 1000, 3000, 5000, 8000, 10 000, 30 000, 60 000.
• · Исходные наборы данных — массивы или файлы соответствующего типа (по № варианта).
• · Проследить динамику роста требуемого для сортировки времени.
• · Проверить, как ведут себя методы на различных входных данных: упорядоченных в прямом порядке, упорядоченных в обратном порядке и случайных.
• · Сравнить теоретические оценки времени сортировки и числа требуемых операций с экспериментальными.
• · Построить соответствующие таблицы и графики сравнительного анализа различных методов сортировки (по времени, размерности и исходной упорядоченности)
• · Провести исследования o для выбранных алгоритмов внутренней сортировки (один из методов вставки и один из методов обменной сортировки)

Теоретические положения.

Сортировка — это процесс упорядочения некоторого множества элементов, на котором определены отношения порядка >, <, ?, ?.

Задачей сортировки является преобразование исходной последовательности в последовательность, содержащую те же записи, но в порядке возрастания (или убывания) значений ключа.

Алгоритмы сортировки оцениваются по скорости выполнения и эффективности использования памяти:

• · Время — характеризует быстродействие алгоритма. Эквивалентно вычислительной сложности. Для типичного алгоритма средняя сложность — O (n log n) и высокая — O (n2). Идеальное поведение для упорядочения — O (n).
• · Память —временное хранение данных. Обычно эти алгоритмы требуют O (log n) памяти. Алгоритмы сортировки, которые не потребляют дополнительной памяти, относят к сортировкам на месте.