Министерство образования и науки Российской Федерации

Государственное образовательное учреждение высшего профессионального образования

Владимирский государственный университет

имени Александра Григорьевича и

Николая Григорьевича Столетовых

(ВлГУ)

Кафедра «Физика и прикладная математика»

Лабораторная работа № 1

по дисциплине

«Алгоритмы и анализ их сложности»

Выполнила:

ст. гр. ИТс-111

Аношин А.В.

Принял:

преподаватель

Курочкин И.В.

Владимир 2011

Цель работы:

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

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

Требуется реализовать 5 алгоритмов сортировки массивов:

• рекуррентное слияние,

• сортировку Шелла,

• пирамидальную сортировку,

• быструю сортировку,

• цифровую сортировку целых неотрицательных чисел.

Программа должна последовательно выполнять все 5 сортировок для одинаковых массивов целых неотрицательных чисел по заданной длине и типу массива. Типы массивов:

• упорядоченные по возрастанию,

• упорядоченные по убыванию,

• случайные.

Каждая сортировка должна завершаться вычислением времени работы и проверкой упорядоченности полученного массива.

Для составленных алгоритмов нужно провести сравнение быстродействия всех сортировок при размерности массивов в 50000, 100000, 500000, 1000000, 5000000, 10000000 элементов и построить графики зависимости времени работы от числа точек (в Excel). Сделать предположение о характере зависимости времени сортировки от размерности массива (квадратичный, субквадратичный, логарифмический, линейный и т.д.).

Краткая теория:

Рекуррентное слияние

Алгоритм рекуррентного слияния основан на сортировке методом слияний. Сортировка методом слияния позволяет сливать два упорядоченных массива в один с сохранением упорядоченности. Упорядоченным называется целочисленный массив с расположенными по неубыванию или по невозрастанию значениями элементов. Задача слияния двух входных упорядоченных массивов А и В состоит в формировании упорядоченного выходного массива С, содержащего все элементы из входных массивов.

Рассмотрим алгоритм слияния для упорядоченных по неубыванию массивов. Вначале элемент А[1] сравнивается с элементом В[1] и наименьший из них записывается в массив С. Если наименьшим был А[1], то на следующем шаге сравниваются А[2] и B[1], а если наименьшим был B[1], то будут сравниваться A[1] и B[2] и т.д. Если на очередном шаге окажется, что из одного входного массива все элементы переписаны в С, то переписывается элемент из другого массива.

Рекурсивная сортировка слиянием организуется с помощью следующей рекурсивной1 процедуры:

• если длина сортируемого массива 1, то ничего не делается;

• в противном случае массив делится на две одинаковые (или почти одинаковые) части, к каждой части применяется алгоритм сортировки2, после чего эти упорядоченные части сливаются в один упорядоченный кусок.

Сортировка Шелла

Сортировка Шелла является усовершенствованным вариантом сортировки вставками. В ходе сортировки вставками создается новый массив, в который мы последовательно вставляются элементы из исходного массива3 так, чтобы новый массив был упорядоченным. Вставка происходит следующим образом: в конце нового массива выделяется свободная ячейка, далее анализируется элемент, стоящий перед пустой ячейкой (если, конечно, пустая ячейка не стоит на первом месте), и если этот элемент больше вставляемого, то элемент сдвигается в свободную ячейку (при этом на том месте, где он стоял, образуется пустая ячейка) и сравнивается следующий элемент. В результате на каком-то шаге возникает ситуация, когда элемент перед пустой ячейкой меньше вставляемого, или пустая ячейка стоит в начале массива. Тогда вставляемый элемент помещается в пустую ячейку. Таким образом, по очереди вставляются все элементы исходного массива. Очевидно, что если до вставки элемента массив был упорядочен, то после вставки перед вставленным элементом расположены все элементы, меньшие его, а после – большие. Так как порядок элементов в новом массиве не меняется, то сформированный массив будет упорядоченным после каждой вставки. А значит, после последней вставки будет получен упорядоченный исходный массив.

Сортировка Шелла – это фактически сортировка вставками с предварительными «грубыми» проходами, которые продвигают элементы сортируемого массива максимально близко к соответствующим им позициям, так что в последней стадии число перемещений будет весьма невелико, поскольку последовательность и так почти отсортирована. Ускорение подтверждено многочисленными исследованиями и на практике оказывается довольно существенным.

Пирамидальная сортировка.

Алгоритм пирамидальной сортировки состоит из двух этапов:

1. Построение пирамиды.

2. Собственно сортировка.

Рассмотрим первый этап. Пирамида представляет собой дерево, в котором каждый узел имеет не более двух потомков, причем узел всегда больше или равен своим потомкам (таким образом, на вершине дерева всегда находится наибольший элемент).

Если в исходном массиве n элементов, то последние (n / 2) элемента становятся основанием пирамиды (эти элементы являются листьями дерева, т.е. у них нет потомков, поэтому для них вышеуказанное правило выполняется автоматически).

Удобнее всего поместить пирамиду в массив. При этом распределение индексов массива по узлам дерева будет выглядеть так (на этом рисунке все цифры – это индексы элементов массива, а не значения этих элементов):

Таким образом, для того, чтобы каждый узел дерева был больше своих потомков, каждый элемент массива a[i] должен быть больше или равен элементам a[2 * i + 1] и a[2 * i + 2].

После завершения построения пирамиды, выполняется сортировка. В этой части алгоритма мы перемещаем в конец массива максимальный элемент, затем исключаем его из дальнейшего процесса сортировки. Поскольку максимальный элемент всегда находится на вершине пирамиды, мы должны поменять местами элементы a[0] и a[n-1] (т.е. последний элемент). Причем элемент a[n-1] необходимо добавлять так, чтобы не нарушился порядок пирамиды (при этом пирамиду придется частично перестроить). Далее мы будем рассматривать массив только до (n-2)-го элемента.

На следующем шаге мы меняем местами a[0] и a[n-2] и далее рассматриваем массив только до (n-3)-го элемента. Повторяем всю эту процедуру до тех пор, пока в рассматриваемой части массива не останется один элемент.