Файл: Алгоритмы и анализ сложности Алгоритмы сортировки.pptx

Сортировка слиянием
Массив разбивается в группы по 1 элементу.
Каждые 2 соседние группы упорядоченно соединяются (операция «слияния») в группу большего размера.
Шаг 2 повторяется до тех пор, пока весь массив не станет 1 группой.

Алгоритм операции «слияния»:

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

Пример. Сложность алгоритма:

Всего выполняется log2n шагов.

На каждом шаге – n операций сравнения.

Итого: n log2n

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

Опр. Массив с индексом 1,…,n называется кучей, если для всех k выполняется: a[k] ≤ a[2k], a[k] ≤ a[2k+1].

1) Алгоритм построения кучи:

Пусть элементы с индексами n/2+1,…,n в массиве имеют структуру кучи.
Проверяем, удовлетворяет ли элемент a[k] (k ≤ n/2) структуре кучи.
Если да, то добавляем его к построенной части. Если нет, то меняем местами a[k] и min{a[2k],a[2k+1]}.

Пример. Структура «куча» Хранение в массиве

Пирамидальная сортировка
Меняем местами элементы a[1] и a[n]. В итоге, самый маленький элемент – в конце массива.
Перестраиваем «кучу» на элементах a[1],…,a[n-1].
Меняем местами элементы a[1] и a[n-1]. Повторяем пункты 1 и 2. И так далее.

Количество проходов = ?

Количество сравнений во время 1 прохода ≤ ?

Количество проходов (перестроений) = ?

Количество сравнений во время 1 перестроения ≤ ?

Количество проходов = n/2

Количество сравнений во время 1 прохода ≤ log2n

Количество проходов (перестроений) = n-1

Количество сравнений во время 1 перестроения ≤ log2n

Итоговая сложность n log2n

Быстрая сортировка
Выбираем эталонный элемент e (первый, последний, случайный)
Производим перераспределение элементов массива на 3 группы: <e, =e, >e
Вызываем быструю сортировку для первой и третьей группы.

Алгоритм перераспределения элементов:

Просматриваем слева в поисках первого элемента, который больше e.
Просматриваем справа в поисках первого элемента, который меньше e.
Меняем найденные элементы местами.
Продолжаем движение с тех элементов, на которых остановились.

Пример.

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

Пример.

Оценка сложности:

В худшем случае – O(n2)

В среднем случае – O(n log2n)

? Достоинства и недостатки алгоритма определить самостоятельно.

Карманная сортировка

Опр. Карманами будем называть m стеков, занумерованных числами 0,…,m-1.

Пусть имеется массив целых чисел, записанных в m-ичной системе счисления и имеющих в своей записи не более, чем k цифр.

Сортировка состоит из k фаз.

На i-той (i=1,…,k) фазе выполняются действия:

перебираем по очереди элементы массива; каждое очередное число заносится в стек с тем номером, какая цифра стоит на i-том с конца месте.
После того, как все числа распределены по карманам, производим объединение стеков в следующем порядке: 0-ой, 1-ый, 2-ой и т.д.

После k-ой фазы массив будет полностью отсортирован.

Карманная сортировка

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

Количество фаз = ?

Количество операций во время каждой фазы = ?

? При каком наборе чисел алгоритм наиболее эффективен?

? При каком наборе чисел эффективность алгоритма минимальна?

Карманная сортировка

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

Количество фаз = k

Количество операций во время каждой фазы = n

Алгоритм эффективен, если в массиве большое количество одинаковых чисел.

Эффективность алгоритма минимальна, если все числа в массиве различны.

Для записи таких чисел требуется не меньше, чем logmn разрядов.

Сложность алгоритма в этом случае = n* logmn

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

Внешняя сортировка применяется к данным, которые расположены на внешних носителях и целиком не помещаются в оперативную память.

Особенность алгоритмов: должны быть построены на принципе последовательного, а не произвольного доступа.

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

Опр. Последовательность элементов, упорядоченных по ключу, называется серией.

Наиболее известные алгоритмы внешней сортировки:

Сортировки слиянием (принцип – распределение и слияние)
Улучшенные сортировки (многофазная и каскадная сортировки).

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

Исходные данные разбиваются на 2 вспомогательных файла.
Из вспомогательных файлов данные сливаются обратно с образованием из одиночных элементов упорядоченных пар.
Повторяем п.1 и 2. теперь упорядоченные пары преобразуются в упорядоченные четверки. И так далее.