1. Лабораторная работа - Методы сортировки

Цель работы: ознакомление с алгоритмами сортировки линейных и нелинейных структур и методикой оценки эффективности алгоритмов.

Продолжительность работы: - 2 часа.

1. Теоретические сведения

Упорядочение элементов множества в возрастающем или убывающем порядке называется сортировкой.

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

Алгоритмы сортировки можно разбить на следующие группы:

Методы сортировки

Турнирная

Пирамидальная

Простая Простой Стандартный

вставка выбор обмен

Бинарная Метод

Лабораторный практикум по курсу « Структуры и алгоритмы обработки данных » Оглавление

1 Теоретические сведения 5

2 Сортировка выбором 6

3 Сортировка вставкой 6

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

5 Быстрая сортировка (сортировка Хоара) 11

6 Сортировка в нелинейных структурах 12

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

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

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

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

9 Пояснения к выполнению работы. 16

10 Теоретические сведения 18

11 Последовательный поиск. 18

12 Бинарный поиск. 18

13 Фибоначчиев поиск. 19

14 Интерполяционный поиск. 20

15 Поиск по бинарному дереву. 21

16 Поиск по сбалансированному дереву. 22

17 Поиск по бору 23

18 Поиск хешированием 24

19 Алгоритмы поиска словесной информации 25

.19.1 Алгоритм Кнута - Морриса - Пратта 25

.19.2 Алгоритм Бойера - Мура 26

.19.3 Алгоритм Рабина 27

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

21 Теоретические сведения 30

22 Итеративный алгоритм. 30

.22.1 Итеративное вычисление факториала 30

.22.2 Рекурсивное вычисление факториала 31

23 Рекурсивные структуры данных 32

.23.1 Формирование бинарного дерева 36

.23.2 Рекурсивная процедура обхода узлов дерева сверху-вниз 36

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

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

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

27 Литература 38

28 Теоретические сведения 39

29 Алгоритмы Крускала и Прима 40

.29.1 Пример со схемой микрорайона 42

.29.2 Пример со схемой компьютерной сети 44

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

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

32 Литература 45

33 Задание к лабораторной работе 4 46

34 Решение задач 49

35 Теоретические сведения 51

36 Метод динамического программирования. 51

37 Пример определения кратчайшего пути №1 52

38 Пример нахождения кратчайшего пути при условии, что граф неориентированный№2 54

39 Метод Дейкстры 56

40 Алгоритм Флойда 58

41 Алгоритм Йена 60

42 Алгоритм Беллмана- Форда 61

43 Литература 61

44 Лабораторное задание. 62

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

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

.46.1 Задание 1: Найти кратчайший путь на графе между тремя парами вершин методом динамического программирования 64

.46.2 Задание 2: Найти кратчайший путь между тремя парами вершин методом Дейкстры 68

47 Решение задач 72

48 Задание на разработку программы 74

49 Теоретические сведения 79

50 Волновой алгоритм 79

51 Двухлучевой алгоритм. 80

52 Четырехлучевой алгоритм 81

53 Маршрутный алгоритм. 81

54 Геометрическая модель задачи о лабиринте 83

55 Алгоритмы составления расписания. 85

56 Литература 87

57 Лабораторное задание. 87

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

59 Решение задач 88

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

вставка Шелла

Метод

Хоара

Обычно сортируемые элементы множества называют записями и обозначают через

k₁, k₂, …,k_n .

2. Сортировка выбором

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

Например, требуется найти минимальный элемент списка:

{5, 11, 6, 4, 9, 2, 15, 7}

Процесс выбора показан на рис.1, где в каждой строчке выписаны сравниваемые пары. Выбираемые элементы с меньшим весом обведены кружком. Нетрудно видеть, что число сравнений соответствует на рисунке числу строк, а число перемещений – количеству изменений выбранного элемента.

{5, 11, 6, 4, 9, 2, 15, 7}

Рис.1. Сортировка выбором

Выбранный в исходном списке минимальный элемент размещается на предназначенном ему месте несколькими способами:

• Минимальный элемент после i-го просмотра перемещается на i-ое место нового списка (i = 1, 2, .… , n), а в исходном списке на место выбранного элемента записывается какое-то очень большое число, превосходящее по величине любой элемент списка, при этом длина заданного списка остаётся постоянной. Изменённый таким образом список можно принимать за исходный.

• Минимальный элемент записывается на i-ое место исходного списка (i = 1, 2, .… , n), а элемент с i-го места - на место выбранного. При этом очевидно, что уже упорядоченные элементы (а они будут расположены, начиная с первого места ) исключаются из дальнейшей сортировки, поэтому длина каждого последующего списка (списка, участвующего в каждом последующем просмотре) должна быть на 1 элемент меньше предыдущего.

• Выбранный минимальный элемент, как и в предыдущем случае, перемещается на i-ое место заданного списка, а чтобы это i-ое место освободилось для записи очередного минимального элемента, левая от выбранного элемента часть списка перемещается вправо на одну позицию так, чтобы заполнилось место, занимаемое до этого выбранным элементом.

Сложность метода сортировки выбором порядка O(n²).

3. Сортировка вставкой

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

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

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

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

Этапы:

Рис. 2. Сортировка вставкой

На первом этапе сравниваются два начальных элемента. Поскольку второй элемент меньше первого, он перемещается на место первого элемента, который сдвигается вправо на одну позицию. Остальная часть последовательности остаётся без изменения. На втором этапе из неупорядоченной последовательности выбирается элемент и сравнивается с двумя упорядоченными ранее элементами. Так как он больше предыдущих, то остаётся на месте. Затем анализируются четвёртый, пятый и последующие элементы – до тех пор, пока весь список не будет упорядоченным, что имеет место на последнем (седьмом) этапе.

Разновидностью сортировки вставкой является метод фон Неймана. Пусть заданы два упорядоченных по возрастанию элементов одномерных массива: а размерности n и b размерности m. Требуется получить третий массив с размерности n+m, который содержал бы все элементы исходных массивов, упорядоченных по возрастанию.

Алгоритм решения этой задачи ,известный как «сортировка фон Неймана» или сортировка слиянием, состоит в следующем: сначала анализируются первые элементы обоих массивов. Меньший элемент переписывается в новый массив. Оставшийся элемент последовательно сравнивается с элементами из другого массива. В новый массив после каждого сравнения попадает меньший элемент. Процесс продолжается до исчерпания элементов одного из массивов. Затем остаток другого массива дописывается в новый массив. Полученный новый массив упорядочен таким же образом, как исходные.

Сложность метода сортировки вставкой порядка O(n²).

Сортировка обменом

Сортировка обменом – метод, в котором элементы списка последовательно сравниваются между собой и меняются местами в том случае, если предшествующий элемент больше последующего.

Требуется, например, провести сортировку списка методом стандартного обмена или методом ’пузырька’ :

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

Обозначим квадратными скобками со стрелками обмениваемые элементы, а - сравниваемые элементы. Первый этап сортировки показан на рис.3, а второй этап – на рис.4.

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

Второй просмотр выявляет максимальный элемент, равный 75 (рис.4).

Процесс сортировки продолжается до тех пор, пока не будут сформированы все элементы конечного списка, либо не выполнится условие Айверсона.

Исходный список	40	11	83	57	32	21	75	64
Первый просмотр	11	40 40	83 57	83 32	83 21	83 75	83 64	83
Полученный список	11	40	57	32	21	75	64

Рис. 3. Сортировка обменом (первый просмотр )

Исходный список	11	40	57	32	21	75	64
Второй просмотр	11	40 40	57 32	57 21	57 57	75 64	75
Полученный список	11	40	32	21	57	64

Рис. 4. Сортировка обменом (второй просмотр )

Условие Айверсона: если в ходе сортировки при сравнении элементов не было сделано ни одной перестановки, то множество считается упорядоченным (условие Айверсона выполняется только при шаге d=1).

Модификацией сортировки стандартным обменом является шейкерная или челночная сортировка . Здесь, как и в методе пузырька проводится по парное сравнение элементов . При этом первый проход осуществляется слева направо, второй – справа налево и т.д. Иными словами меняется направление просмотра элементов списка.

Сложность метода стандартного обмена O(n²).