Исследование алгоритмов сортировки массивов

Министерство образования Республики Беларусь

Учреждение образования

Факультет

Кафедра

Дисциплина:

ОТЧЁТ

по лабораторной работе №2

Тема работы: Исследование алгоритмов сортировки массивов

Выполнил

студент:

Проверил:                                                                                            

содержание

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

2 Методика решения задачи        4

3 Описание алгоритмов решения задачи        6

4 Структура данных        7

4.1 Структура данных программы        7

4.2 Структура данных алгоритма Swap        7

4.3 Структура данных алгоритма Fill        7

4.4 Структура данных алгоритма BubbleSort        8

4.5 Структура данных алгоритма HeapSort        8

4.6 Структура данных алгоритма SiftDown        9

5 Схема алгоритма решения задачи по ГОСТ 19.701-90        10

5.1 Схема алгоритма решения задачи        10

5.2 Схема алгоритма Swap        11

5.3 Схема алгоритма Fill        12

5.4 Схема алгоритма BubbleSort        13

5.5 Схема алгоритма HeapSort        14

5.6 Схема алгоритма SiftDown        15

6 Результаты расчетов        16

Приложение А        17

Приложение Б        21

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

Провести сравнительный анализ по числу перестановок следующих видов сортировки:

1. Метод выбора;
2. Сортировка Шелла.

Размерности массивов соответственно: 100, 250, 500, 1000, 2000, 3000.

Типы массивов:

1. Случайный;
2. Отсортированный;
3. Перевернутый.

1. Методика решения задачи

1. Подготовка массивов

Для каждой размерности N генерируется массив по определённым правилам.

Сразу отсортированный масив создаётся посредством присваивания его элементам значений, равных индексам элементов:

A[I]:=I

Отсортированный в другую сторону масив создаётся ровно наоборот:

A[I]:=N-I

        Случайный массив генерируется посредством присваивания его элементам случайных значений в диапазоне от 1 до верхней границы массива:

[I]:=Random(N)

1. Подсчёт перестановок

После создания массивов начинается сортировка с подсчётом значений. Чтобы подсчёт проходил в равных условиях, массив предварительно копируется, а затем задействуется во втором виде сортировки.

Каждое сравнение увеличивает число сравнений на 1; если же сравнение сложное, т.е. содержащее логические операции or, and и так далее, то количество сравнений наращивается столько раз, сколько частей содержится в сравнении.

1. Сортировки

Пузырёк с флажком является улучшенной сортировкой обменами. Суть заключается в том, что на каждой итерации осуществляется проверка, была ли хоть одна перестановка в процессе итерации. Если перестановок не было, сортировка прекращается. Таким образом, отсортированный заранее массив не будет сортироваться как положено, а будет проверен целиком всего один раз.

Пирамидальная сортировка является улучшенной сортировкой выбором. В сортировке выбором больше всего времени уходит на поиск максимального элемента в неотсортированной части. Пирамидальная сортировка лишена этого недостатка, поскольку на каждой итерации она сохраняет больше информации, формируя бинарную кучу. Бинарная куча – это граф-дерево, каждый узел которого может иметь не более двух потомков. 

В нашем случае это не бинарное дерево в прямом смысле, а обычный массив, элементы которого мысленно имеют свою роль: для каждого элемента i есть элементы 2i+1 и 2i+2 , принятые за левый и правый дочерний.