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

Сортировка

Фундаментальная алгоритмическая задача программирования
Сортировка (общий случай) – процесс перегруппировки заданного множества

Алгоритм сортировки

Практически любой алгоритм сортировки можно разбить на 3 части:
сравнение, определяющее

Оценка алгоритмов сортировки

Время сортировки
Память
Устойчивость
Естественность поведения

Классификация сортировок

По различным признакам:
по количеству использований операций сравнения
по потребности в дополнительной

Внутренняя и внешняя сортировка

Внутренняя сортировка (англ. internal sort) — сортировка данных,

Различия м\у внеш. и внутр. сортировкой

Когда используются методы внутренней сортировки:
Если сортируемый

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

Алгоритмы внутренней сортировки (элементарные методы)
Сортировка выбором
Сортировка вставкой
Пузырьковая сортировка
…
Алгоритмы внутренней сортировки

Раздел Алгоритмы внутренней сортировки

Внутренняя сортировка

Квадратичные и субквадратичные алгоритмы
Сортировка выбором (SelectSort)
Сортировка пузырьком (BubbleSort) и ее

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

Шаги алгоритма:
Находим минимальное значение в текущей последовательности.
Производим обмен этого значения

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

Неестественнен

Неустойчив

Еще пример сортировки выбором

Шаги алгоритма:
Находим минимальное значение в текущей последовательности.
Производим обмен

Код сортировка выбором

Сортировка пузырьком

Код сортировки пузырьком

Сложность O(n2)

Модификации сортировки пузырьком

Улучшение 1: запоминать производился ли на данном проходе какой-либо

Сортировка пузырьком Выводы

Среднее (оно же худшее) количество операций остается квадратичным.
Дополнительная память, очевидно,

«Шейкер-сортировка»

Глупая сортировка

Сложность O(n3)

Сортировка вставками

Код сортировки вставками

Сложность O(n2)

Сортировка вставками со сторожевым элементом

Сортировка методом Шелла

Общая схема метода состоит в следующем.
Шаг 1. Происходит упорядочивание

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

Шаг 0: исходный массив

Шаг 1: сортируем вставками
8 групп по

Модификации сортировки методом шелла (Седжвик)

8, 4, 2, 1

inc[s-1], если 3*inc[s] >

Код сортировки методом Шелла + Седжвик

Пример сортировка методом Шелла

Демонстрация сортировки по неубыванию методом Шелла

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

Сравнение времени сортировок
коричневая линия: сортировка пузырьком;
синяя линия: шейкер-сортировка;
розовая линия: сортировка выбором;
желтая

Сложность O(n*log n)

Сложность O(n2)

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

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

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

Пирамида

Пирамида (сортирующее дерево, двоичная куча) – двоичное дерево с упорядоченными листьями

Просеивание

Просеивание – это построение новой пирамиды по следующему алгоритму: новый элемент

Алгоритм пирамидальной сортировки

Алгоритм пирамидальной сортировки.
Шаг 1. Преобразовать массив в пирамиду.
Шаг 2.

Фаза 1. пирамидальной сортировки Построение пирамиды

Шаг.1

Шаг.2

Шаг.3

Шаг.4

Шаг.5

Код фазы 1. построение пирамиды

Фаза 2. Сортировка

Алгоритм фазы 2:
Меняем местами верхний и последний элементы
«Забываем» про

Код фазы 2. сортировка

Альтернативный код пирамидальной сортировки

Характеристики пирамидальной сортировки

Построение пирамиды занимает O(n log n)
Не использует дополнительной памяти
Метод

Быстрая сортировка Хоара

Дан массив x[n] размерности n.
Шаг 1. Выбирается опорный элемент

Алгоритм (псевдокод)

Код быстрой сортировки Хоара

Пример

Пример быстрой сортировки (не симметричный вариант)

0.

0

1

2

3

4

5

6

7

1.

2.

3.

Важно

0.

1.

2.

Быстрая сортировка

Общая схема:
из массива выбирается некоторый опорный элемент a[i],
запускается процедура

Алгоритм быстрой сортировки

На входе массив a[0]...a[N] и опорный элемент p, по

Пример быстрой сортировки (симметричный вариант)

Псевдокод.
quickSort ( массив a, верхняя граница N )

Код быстрой сортировки

Характеристики быстрой сортировки

Быстродействие:
Средний случай: O(n log n)
Худший случай: O(n2)
Использует дополнительную память
Метод неустойчив.
Поведение

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

Слияние – это объединение двух или более упорядоченных массивов в

Пример

Демонстрация сортировки слиянием по неубыванию

Код сортировки слияние

Сложность O(n*log n)

Расходует дополнительную память.
Не устойчив.

Иллюстрация работы разных алгоритмов сортировки

www.sorting-algorithms.com/

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

Сортировка пузырьком (англ. Bubble sort ) — сложность алгоритма: O(n2); для каждой пары индексов

Раздел Алгоритмы внешней сортировки

Алгоритмы внешней сортировки

Прямое слияние
Естественное слияние
Многопутевое слияние
Трехпутевое слияние

Прямое слияние

Предположим, что имеется последовательный файл A, состоящий из записей a1,

Прямое слияние (шаг 1)

В файле A хранятся числа: 8, 23, 5,

Прямое слияние (шаг 2)

Прямое слияние (шаг 3)

Часть 1

Часть 2

Особенности прямого слияния

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

Естественное слияние

При использовании метода прямого слияния не принимается во внимание то,

Естественное слияние (шаг 1)

Естественное слияние (шаг 2)

Особенности естественного слияния

Число чтений/перезаписей файлов при использовании этого метода будет не

Многопутевое слияние

Процесс многопутевого слияния происходит также как и процесс простого прямого

Трехпутевое слияние

Трехпутевое слияние

Шаг 4

Шаг 5

Трехпутевое слияние

Шаг 6

Сбалансированное многопутевое слияние

В основе метода внешней сортировки сбалансированным многопутевым слиянием является

Многопутевое слияние

По мере увеличения длины серий вспомогательные файлы с большими номерами

Улучшение эффективности внешней сортировки

Чем более длинные серии содержит файл перед началом