Добавил:
Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
АиСД. Практикум (in dev).doc
Скачиваний:
167
Добавлен:
29.02.2020
Размер:
4 Мб
Скачать
☆
    1. Сортировка в нелинейных структурах

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

      1. Турнирная сортировка

Свое название эта сортировка получила, потому что она используется при проведении соревнований, турниров и олимпиад. Элементы исходного множества представляются листьями дерева. Их по парное сравнение позволяет определить максимальный элемент.

Пример: Дано исходное множество { 7, 1, 9, 3, 6, 5, 8 }

Производится по парное сравнение элементов снизу- вверх. Найденный максимальный элемент помещается в результирующее множество.

В результате будет получено упорядоченное множество { 9,8,7,6,5,3}

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

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

Пирамидальное дерево – это бинарное дерево обладающее тремя свойствами:

  • В вершине каждой триады располагается элемент с большим весом.

  • Листья бинарного дерева располагаются либо в одном уровне либо в двух соседних

на одном уровне на соседних

уровнях

  • Листья нижнего уровня располагаются левее листьев более высокого уровня.

В ходе преобразования элементы триад сравниваются дважды , при этом

элемент с большим весом перейдет вверх, а с меньшим - вниз.

1 2

1 - первое сравнение

2 - второе сравнение

Пример: Дано исходное множество { 2, 4, 6, 3, 5, 7 }

В результате будет получено упорядоченное множество { 2,3,4,5,6,7 }

    1. Функция сложности алгоритма

Для оценки эффективности алгоритмов используется функция сложности алгоритма, которая обозначается заглавной буквой “О”, в круглых скобках записывается аргумент. Например, функция сложности O(n2) читается как функция сложности порядка n2. Функция сложности алгоритма – это функция, которая определяет количество сравнений, перестановок а так временные и ресурсные затраты на реализацию алгоритма.

Функция сложности принимает следующий ряд значений:

Функция сложности

Чем правее на оси расположена функция сложности, тем сложнее алгоритм.

Лабораторное задание

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

    1. Методика выполнения лабораторной работы

Для проведения лабораторной работы необходимо выполнить следующие действия.

1. Вызвать систему Sort_new, включающую в себя сортировку неупорядоченных списков в линейных и нелинейных структурах.

Путь к файлу: D:\ИПОВС\АиСД\SORT\Sort_new.exe

Система работает в диалоговом режиме с использованием “меню”. Вся необходимая информация во время работы системы отображается на экране дисплея и не требует специальных пояснений.

Основные функции системы

K - конец работы;

? - выдача краткого сообщения о командах;

U – задание условий для генерации неупорядоченного массива;

G - генерации неупорядоченного массива;

P – вывод массива;

W – вывод времени сортировки, количества элементов массива.

Сортировка методом:

1 – простого обмена;

2 – бинарной вставки;

3 – простой вставки;

4 – челночной;

5 – простого выбора;

6 – слиянием;

7 – Шелла;

8 – Хоара;

9 – пирамиды;

Esc – аварийное прерывание выполнения функции.

Краткое описание функции

U– задание условий для генерации неупорядоченного массива (задаются число элементов и границы элементов неупорядоченного массива). Заданные условия сохраняются до следующего вызова функции “U”;

G – генерация неупорядоченного массива, необходима перед каждой сортировкой;

P – вывод массива в текущем состоянии : неупорядоченный (до сортировки) или упорядоченный (после неё);

W - вывод времени сортировки ;

I – 9 – методы сортировки;

Для указанных в лабораторной работе методов сортировки провести следующие исследования:

a) выполнить сортировку массива из N чисел (варианты заданий даны в приложении ; номер варианта соответствует порядковому номеру фамилии студента в списке группы). Результаты занести в таблицу 1.

Таблица 1

Метод

Количество элементов сортируемого

массива N

N1

N2

N3

Время сортировки t, c

t1

t2

t3

2. Провести исследование методов сортировки упорядоченных списков с использованием программы SORTALL.

Путь к файлу: D:\ИПОВС\АиСД\SORT\Sortall.exe

Результаты занести в таблицу 1.

3. Провести исследование методов сортировки с использованием программ

WinSort и Sort.

4. Оценить сложность рассмотренных методов сортировки;

а) провести анализ отклонения полученной в результате эксперимента

сложности алгоритма от теоретической;

б) построить графические зависимости времени сортировки от количества

элементов сортируемого массива.

Требования к отчёту

Отчёт должен содержать:

  1. конспект лабораторной работы;

  2. примеры сортировки ;

  3. результаты выполнения работы;

  4. выводы по работе;

Контрольные вопросы

    1. Что понимается под сортировкой?

2. Каковы особенности сортировки: вставкой, выбором, обменом , Шелла,

Хоара, турнирной, пирамидой?

3. Что включает в себя понятие сложности алгоритма?

4. В чём состоит методика анализа сложности алгоритмов сортировки?

Литература

1. Колдаев В.Д., Поддубная Л. М., Полосухин Б.М. Методы сортировки .

М.:МИЭТ, 1985.

2. Колдаев В.Д., Поддубная Л. М., Полосухин Б.М. Лабораторный практикум по

курсу « Теория алгоритов и вычислительные методы » М.:МИЭТ, 1988

3. Кнут Д. Искусство программирования для ЭВМ. Т. 3. Сортировка и поиск.

М. : Мир, 2000.

4. Т. Кормен, Ч. Лейзерсон, Р. Ривест «Алгоритмы: построение и анализ».

М.: МЦНМО, 2000.

5. Вирт Н. Алгоритмы и структуры данных.: Пер. С англ. - М.: Мир, 2001.

6. Хусаинов Б.С. Структуры и алгоритмы обработки данных. Примеры на языке Си.

Учеб. пособие. М : Финансы и статистика, 2004.

Приложение

Варианты заданий

Вариант

n1

n2

n3

Составить программу

1,15

1000

4000

6000

Простая вставка

2,16

800

3000

7000

Сортировка слиянием

3,17

2000

5000

6800

Метод Шелла

4,18

1500

3500

6000

Простой выбор

5,19

1000

2800

8500

Метод Хоара

6,20

500

2500

6500

Бинарная вставка

7,21

900

3000

8500

Шейкерная сортировка

8,22

1200

2000

7500

Простая вставка

9,23

2500

3500

6500

Шейкерная сортировка

10,24

1600

2800

8800

Метод Шелла

11,25

2200

3400

7200

Простой выбор

12,26

1900

2700

8000

Метод Хоара

13,27

1300

3500

6000

Бинарная вставка

14,28

1700

2800

7500

Сортировка слиянием

Предусмотреть в программе учет времени сортировки для указанных значений n1, n2, n3. Для сортировок Шелла, Хоара, пирамидальной значения n1, n2, n3

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

Произвести расчет функции сложности разработанного алгоритма по полученным временным затратам.