Материал: АиСД. Практикум (in dev)

Рис. 8. Метод Хоара

Теперь начинаем изменять индекс i = i + 1 и сравнивать элементы k_i и k₀. Продолжаем увеличение i до тех пор, пока не получим условие k_i > k₀, после чего следует обмен k_i и k₀ (см.шаг5). Снова возвращаемся к индексу j, уменьшаем его. Чередуя уменьшение j и увеличение i, продолжаем этот процесс с обоих концов к середине до тех пор, пока не получим i = j (см.шаг 7).

В отличие от предыдущих рассмотренных сортировок уже на первом этапе имеют место два факта: во-первых, базовый ключ k₀ = 40 занял своё постоянное место в сортируемой последовательности; во-вторых, все элементы слева от k₀ будут меньше него, а справа- больше него. Таким образом, по окончании первого этапа имеем:

21, 11, 32 40 57, 83, 75, 64

левая часть правая часть

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

Сложность метода Хоара O(n log₂n).

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

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

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

1 2

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

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

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

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

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

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

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

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

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

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

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

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

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

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. Для сортировок Шелла, Хоара, пирамидальной значения n1, n2, n3

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

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