Лабораторная работа 2-8 сортировка

Лабораторная работа № 2-8. Алгоритмы сортировки.

Цель работы: Изучение различных алгоритмов сортировки массивов.

1. Основные понятия и определения

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

Под сортировкой принято понимать процесс перегруппировки заданного множества объектов в заданном порядке.

Цель: Облегчить последующий поиск объектов в таком отсортированном множестве.

Можно выделить два алгоритма:

1.Сортировка массивов (внутренняя сортировка)

Сортируются данные которые все сразу находятся в оперативной памяти компьютера.

2. Сортировка файлов, последовательностей (внешняя сортировка) Сортируются данные, находящиеся на внешних носителях.

При внутренней сортировке стараются уменьшить число сравнений ключа и уменьшить число перемещений записей.

Ключ – это некий признак каждого элемента, по которому ведется сортировка. При внешней сортировке решающим фактором эффективности алгоритма

является количество обращений к внешним устройствам (время).

Сортировка – это перестановка элементов массива А в массив A’ для которого эти элементы будут каким-то образом переставлены

Т.о.чтобы для некоторой упорядочивающей функции f выполнялось соотноше-

1

ние:

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

Задача сортировки массива А заключается в том, чтобы найти такую перестановку элементов исходного массива А в массив A’, чтобы ключи этих элементов располагались в неубывающем порядке:

Алгоритмы будем использовать такие, которые позволяют новый отсортированный массив хранить на месте старого.

Адресная сортировка – это сортировка, при которой мы перемещаем не сами элементы, а создаем массив ключей, который говорит о порядке выбора элементов исходного массива А в соответствии с правилом (3) или (4).

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

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

•Методы, основанные на выборе (selection).

•Методы, основанные на обмене (exchange).

•Метод прямого включения (insertion).

2.Алгоритмы сортировки

2.1. Методы, основанные на выборе

Данная группа алгоритмов основана на следующих принципах:

1.Выбираем из исходного массива элемент с наименьшим ключом.

2.Этот элемент меняется местом с первым элементом.

3.Затем этот процесс повторяется для n–1 элемента.

Под ключом элемента мы будем понимать его значение.

2

Сортировка, основанная на выборе

Массив зададим следующим образом A(1 To N) ‘ вводятся значения элементов массива

Next i

‘ печать отсортированного массива Число сравнений ключей для данного алгоритма оценено теоретически и равно:

Число перестановок ключей при начальном практически упорядоченном массиве равно

При большом числе элементов (~ 200 – 400) – алгоритм работает медленно. Данный алгоритм хотя и не самый быстрый, но зато самый простой.

3

2.2. Методы обмена

Метод пузырька (BUBBLE)

Если массив будем располагать вертикально, то элементы A(i) можно интерпретировать как пузырьки, находящиеся в сосуде с водой, причем вес каждого пузырька равен значению этого элемента.

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

Массив будем задавать следующим образом A(1 To N)

x = A(j–1) A(j–1) = A(j) A(j) = x

End If

Next j

Next i

‘ Печать сортированного массива

Достоинства

1.простота

2.наглядность

Недостатки

Процесс сортировки очень сильно замедляется с ростом N

4

Число сравнений ключей для данного алгоритма оценено теоретически и равно:

A(j) = x k = j End If Next j

5

R = k - 1 Wend

‘ печать сортированного массива

2.3. Методы включения

Метод прямого включения

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

Процесс просеивания заканчивается, если

•найден элемент aj с индексом меньшим, чем ключ у x,

•достигнута левая граница готовой последовательности.

Массив имеет на 1 индекс больше по сравнению с предыдущими сортировками

A(0 To N). For i = 2 To N x = A(i)

A(0) = x j = i While

Wend

A(j) = x

Next i

‘ печать сортированного массива

Достоинства

Не требуется дополнительной памяти.

Недостатки

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

6

Среднее число сравнений и перестановок равно

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

Двоичное включение

Относится к улучшенным методам сортировки.

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

For i = 2 To N x = A(i)

L = 1 R = i

While L < R

m = (L + R) / 2

If A(m) <= x Then L = m + 1

Else R = m End If

Wend

For j = i To R + 1 A(j) = A(j–1)

7

Next j A(R) = x Next i

‘ вывод сортированного массива Общее число сравнений и присваиваний

Для двоичного включения место включения обнаружено, если L = R. Т.о. интервал должен быть единичной длины. Число сравнений практически не зависит от начального порядка элементов. Однако из-за того, что при делении происходит отбрасывание дробной части, истинное число сравнений может оказаться на 1 больше. В нижней части последовательности место включения отыскивается в среднем несколько быстрее, чем в верхней части, поэтому предпочтительнее ситуация, в которой элементы немного упорядочены.

2.4. Сортировка всплытием Флойда

Сортировка с помощью дерева (см. рис. 1).

Упорядоченное двоичное дерево – дерево в котором в каждой его вершине значение не меньше, чем значение в его дочерних вершинах (см. рис. 2).

Рис. 1. Дерево (1- корень, 2 и 3 - до- Рис. 2. Упорядоченное дерево. черние для 1 вершины, 4,5,6 и 7 - дочерние для 2 и 3 вершины).

Двоичное дерево называется частично упорядоченным, если свойство упо-

8

рядоченности выполняется для каждой из его дочерних вершин, однако, для корня это свойство нарушается.

Исходная последовательность или массив представляются виде двоичного дерева в памяти в виде одномерного массива (см. рис. 3). В таком дереве ветви (листья, ребра) присутствуют неявно и вычисляются с помощью арифметических операций над индексами элементов массива (см. рис. 4).

A1

A(k)

A2 A3

Рис. 3. Дерево Рис. 4. Индексы массива Основу алгоритма всплытия составляет процедура, которая работает с под-

деревом A(i To k) и преобразует почти упорядоченное поддерево в упорядочен-

ное за O( N log2 N ) сравнений.

Процедура всплытия

Sub Surface ( A() As Long, ByVal i, k As Integer) Dim j, m, temp As Long

m = 2 * i temp = A(i)

While m <= k

If m = k Then j = m

Else If A(m)>A(m+1) Then j=m Else j = m +1

End If

End If

If A(j) > temp Then A(i) = A(j) i = j

9

A(i) = temp End Sub

Сложность процедуры всплытия

1.Во время всплытия на каждом уровне выполняется конечное число операций сравнения C.

2.Если посчитать число подуровней (H – высота дереве), то количество операций сравнения будет равно C*H.

3.Высота двоичного дерева определяется исходя из следующих соображе-

Необходимо выполнить саму процедуру всплытия Флойда, для каждого поддерева

For k = N To 2 Step –1 Surface(), 1, k

temp = A(k) A(k) = A(1) A(1) = temp

Next k

10