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

Сравнительный анализ методов сортировки

Техническое задание.
Для проведения экспериментального сравнительного анализа различных методов сортировки необходимо разработать программу, которая в автоматическом режиме подсчитывала бы время, требуемое для каждого метода сортировки. Для чистоты эксперимента сортировка всеми методами должна проводиться на одинаковых наборах входных данных, затем должен формироваться новый набор данных, и они опять должны подвергаться сортировке различными методами. Таким образом необходимо выполнить 60 циклов сортировки, подсчитать среднее время, которое потребовалось каждому методу, чтобы отсортировать входной массив. Для более полного анализа методов в каждом цикле сортировки сортировка должна проводиться для размерностей 500, 1000, 3000, 5000, 8000, 10000, 30000, 60000. Это даст возможность проследить динамику роста требуемого для сортировки времени. Также необходимо проверить, как ведут себя методы на различных входных данных: упорядоченных в прямом порядке, упорядоченных в обратном порядке и случайных.

Методические указания.
Традиционно различают внутреннюю сортировку, в которой предполагается, что данные находятся в оперативной памяти, и важно оптимизировать число действий программы (для методов, основанных на сравнении, число сравнений, обменов элементов и пр.), и внешнюю, в которой данные хранятся на внешнем устройстве с медленным доступом (магнитные лента, барабан, диск) и прежде всего надо снизить число обращений к этому устройству.
В этой работе рассмотрим алгоритмы внутренней сортировки массивов элементов, так как они более важны большинству программистов в повседневной практике.
Стоит заметить, что алгоритм сортировки слиянием удобно применять и при сортировке внешних данных. При этом речь будет идти о слиянии файлов.
При рассмотрении алгоритмов сортировки прежде всего нас будет интересовать максимальная и средняя сложности метода, так как именно они, как правило, важны на практике. Максимальная сложность показывает поведение алгоритма в худшем случае, а средняя сложность - наиболее вероятное поведение при увеличении размера сортируемого массива. Сводные данные о сложности рассматриваемых методов можно найти в приложении 2 в конце работы.
Начнем разбор алгоритмов.

Сортировка подсчетом.
Суть метода заключается в том, что на каждом шаге мы подсчитываем, в какую позицию результирующего массива надо записать очередной элемент исходного массива. Выглядит это так:
for i := 1 to N do
begin
<вычислить_место_k+1_элемента_A[i]
в_результирующем_массиве_B>
B[k+1] := A[i];
end;
Слева от B[k+1] должны стоять элементы большие или равные B[k+1]. Значит, число k складывается из количества элементов меньших A[i] и, возможно, некоторого числа элементов, равных A[i]. Условимся, что из равных мы будем учитывать только те элементы, которые в исходном массиве стоят левее A[i]. Теперь вычисление k можно записать следующим образом:
k := 0;
for j := 1 to N do
if (A[i]>A[j])or((A[i]=A[j])and(i>j)) then
Inc(k);
Легко видеть, что этот алгоритм всегда имеет сложности T(n2) (два вложенных цикла, зависящих от n линейно) и O(n) (результирующий массив).
Сортировка включением.
В этой сортировке массив делится на 2 части: отсортированную и неотсортированную. На каждом шаге берется очередной элемент из неотсортированной части и "включается" в отсортированную часть массива.
Простое включение.
Пусть отсортировано начало массива A[1], A[2], ..., A[i-1], а остаток массива A[i], ...,A[n] содержит неотсортированную часть. На очередном шаге будем включать элемент A[i] в отсортированную часть, ставя его на соответствующее место. При этом придется сдвинуть часть элементов, больших A[i], (если таковые есть) на одну позицию правее, чтобы освободить место для элемента A[i]. Но при сдвиге будет потеряно само значение A[i], поскольку в эту позицию запишется первый (самый правый - с самым большим индексом) сдвигаемый элемент. Поэтому прежде чем производить сдвиг элементов необходимо сохранить значение A[i] в промежуточной переменной.
Так как массив из одного элемента можно считать отсортированным, начнем с i=2.
Программа будет выглядеть так:
for i := 2 to n do
begin
Tmp := A[i];
j := i-1;
while (A[j]>Tmp)and(j>1) do
begin
A[j+1] := A[j];
Dec(j)
end;
A[j+1] := Tmp;
end;
Этот алгоритм также имеет максимальную и среднюю сложности T(n2), но в случае исходно отсортированного массива внутренний цикл не будет выполняться ни разу, поэтому метод имеет Tmin(n). Можно заметить, что метод использует любой частичный порядок, и чем в большей степени массив исходно упорядочен, тем быстрее он закончит работу. В отличие от предыдущего метода, этот не требует дополнительной памяти.
Метод Шелла.
Метод Шелла является усовершенствованием простого включения, которое основано на том, что включение использует любой частичный порядок. Но недостатком простого включения является то, что во внутреннем цикле элемент A[i] фактически сдвигается на одну позицию. И так до тех пор, пока он не достигнет своего места в отсортированной части. (На самом деле мы избавлялись от сдвига A[i], сохраняя его в промежуточной переменной, но сути метода это не изменяло, так как передвигалось место, оставленное под сохраненное значение). Метод Шелла позволяет преодолеть это ограничение следующим интересным способом.
Вместо включения A[i] в подмассив предшествующих ему элементов, его включают в подсписок, содержащий элементы A[i-h], A[i-2h], A[i-3h] и так далее, где h - положительная константа. Таким образом формируется массив, в котором "h- серии" элементов, отстоящих друг от друга на h, сортируются отдельно.
Конечно, этого недостаточно: процесс возобновляется с новым значением h, меньшим предыдущего. И так до тех пор, пока не будет достигнуто значение h=1.
В настоящее время неизвестна последовательность hi, hi-1, hi-2, ..., h1, оптимальность которой доказана. Для достаточно больших массивов рекомендуемой считается такая последовательность, что hi+1=3hi+1, а h1=1. Начинается процесс с hm-2, где m - наименьшее целое такое, что hm_ n. Другими словами hm-2 первый такой член последовательности, что hm-2_ [n/9].
Теперь запишем алгоритм: