Алгоритмы сортировки массивов. Лекция 5

1.

Лекция 5. Алгоритмы сортировки массивов.
1. Оценка алгоритмов сортировки
2. .Алгоритм сортировки обменами ("пузырьковая" сортировка)
3. Алгоритм сортировки выбором элемента
4. Алгоритм сортировки вставками
5. Алгоритм сортировки слиянием
6. Алгоритм сортировки методом Шелла
7. Алгоритм быстрой сортировки Хоара
8. Алгоритм пирамидальной сортировки

2.

Оценка алгоритмов сортировки
Алгоритм сортировки - алгоритм для упорядочения некоторого множества
элементов по возрастанию или убыванию.
Ключ сортировки - атрибут (или несколько атрибутов), по значению
которого определяется порядок элементов.
Характеристики алгоритма сортировки
1. Временная сложность
2. Емкостная сложность
3. Устойчивость
4. Естественность поведения

3.

Алгоритм сортировки обменами
("пузырьковая" сортировка)
1. Выбрать переменную-счетчик i = 0.
2. Если i >= n, то конец алгоритма.
3. Выбрать переменную-счетчик j = (n -1) - i.
4. Если a[j] < a[j — 1], то элементы поменять местами.
5. j- - и переход на п.4.
6. Если j > i, то переход на п. 4.
7. i++ и переход на п.2

4.

Оценка сложности алгоритма
сортировка массива (5 4 3 2 1):
Количество
Количество
1-я итерация: 1 5 4 3 2 (4 (n-1)сравнения, 4 (n-1)обмена);
сравнений
обменов
2-я итерация: 1 2 5 4 3 (3 (n-2) сравнения, 3 (n-2) обмена);
3-я итерация: 1 2 3 5 4 (2 (n-3) сравнения, 2 (n-3) обмена); n – 1 + (n – 2) + …1 = n – 1 + (n – 2) + …1
4-я итерация: 1 2 3 4 5 (1 сравнение, 1 обмен).
= n · (n – 1)/2
= n · (n – 1)/2
Всего 10 сравнений и 10 обменов.
Первый член прогрессии a1=0, n-й член прогрессии an=n-1
Сумма арифметической прогрессии Sn =(a1+an)*n/2=n(n-1)/2
Значит алгоритм сортировки «пузырьком» имеет сложность О(n2).
Временная сложность
Емкостная сложность
Устойчивость
Естественность поведения
2
O(n )
M(1)
Да
Нет

5.

Алгоритм сортировки выбором элемента
1. Найти максимальный элемент неотсортированного массива.
2. Если последний элемент в массиве не равен найденному, то поменять их местами.
3. Уменьшить размерность неотсортированного массива на единицу.
4. Если размерность неотсортированного массива равна 1 (массив из 1-го элемента всегда
упорядочен), то конец иначе переход на п.1
сортировка массива (5 4 3 2 1):
1-я итерация: 1 4 3 2 5 (4 сравнения, 1 обмен).
2-я итерация: 1 2 3 4 5 (3 сравнения, 1 обмен).
3-я итерация: 1 2 3 4 5 (2 сравнения, 0 обменов).
4-я итерация: 1 2 3 4 5 (1 сравнение, 0 обменов).
Всего 10 сравнений и 2 перестановки
Временная сложность
Емкостная сложность
Устойчивость
Естественность поведения
2
O(n )
M(1)
Да
Нет
Количество
сравнений
Количество
обменов
n – 1 + (n – 2) + …1 =
n · (n – 1)/2
От 0 до n-1