@ProMaths

1. Написать программу, реализующую сортировку массива заданным способом

(согласно варианту).

2. Сравнить число сравнений (С) и обменов (М) для числовых массивов, содержа-

щих различное число элементов (20, 500, 1000, 3000, 5000, 10000,1000000), выбирае-

мых случайным образом. Оценить время сортировки.

3. Исследовать влияние начальной упорядоченности массива (отсортированный,

отсортированный в обратном порядке, отсортирован случайным образом).

4. Все полученные данные ввести в таблицу 1. Сравнить эффективности сорти-

ровки массивов разной размерности и упорядоченности. Сделать выводы.

Таблица 1

Сравнительная таблица эффективности алгоритма

Массив Показатель N=20 N=100 N=500 N=1000 N=1000000

Упорядоченный

массив

Обратно упоря-

доченный

Случайный

С

M

Время

выполнения

C

M

Время

выполнения

Avr(C)

Avr(M)

Время

выполнения

Т.е. необходимо проделать минимум 15 опытов, в каждом из которых должны

быть определены два числа С и М. В случае случайного массива заранее нельзя пред-

сказать значения показателей эффективности. Естественно, что сравнительный ана-

лиз алгоритмов возможен только по средним значениям (Avr(C) – Average, т.е. сред-

нее значение С). Для этого необходимо провести серию опытов, желательно, 10-15).

Следовательно, алгоритм сортировки должен быть оформлен в виде самостоя-

тельной программной единицы – подпрограммы, которая может быть использована

многократно.

Для некоторых рассмотренных методов сортировки существуют точные фор-

мулы, вычисление которых дает минимальное, максимальное и среднее число срав-

нений ключей С и пересылок элементов массива М.

Таблица 2 содержит данные, приводимые в книге Никласа Вирта

Таблица 2

Сортировка Min Avg Max

Сортировка

вставками

Прямой выбор С ( − )/2 ( − )/2 ( − )/2

C − 1 ( + − 2)/4 ( + )/2 − 1

М 2( − 1) ( − 9 − 10)/4 ( + 3 − 4)/2

M 3( − 1) (() + 0,57) /4 + 3( − 1)

Простой

обмен

C ( − )/2 ( − )/2 ( − )/2

M 0 0,75( − ) 1,5( − )

0