Лекция 2. Сортировки

Август 5, 2022

Главная
Информатика
Лекция 2. Сортировки

Содержание

2. Задача сортировки Алгоритм сортировки — это алгоритм для упорядочивания элементов в списке. В случае, когда элемент
3. Характеристики сортировки Устойчивость -- элементы с равными ключами не меняются местами Локальная -- не требует дополнительной
4. Квадратичные сортировки Сортировка пузырьком Сортировка выбором Сортировка вставками
5. Сортировка слиянием
6. Сортировка с помощью кучи
7. Слияние К отсортированных массивов с помощью кучи
8. TimSort Массив делится на подмассивы разной длины Каждый массив сортируется вставками (или другой устойчивой сортировкой) Отсортированные
9. TimSort Выберем значение minrun -- минимального размера подмассива, на которые будет делиться массив (желательно, чтобы n/minrun
10. TimSort Начинаем процедуру слияния: Заведём стек пар {Индекс начала подмассива, Размер} Добавляем очередной подмассив Пусть X,Y,Z
11. Быстрая сортировка Массив a[i;j] разбивается на два подмассива a[i;k], a[k+1;j] так, что для любого x из
12. Быстрая сортировка Опорный элемент -- значение ключа, относительно которого разбивается массив на каждом шаге. Выбор опорного
13. Среднее время работы Лемма: время работы быстрой сортировки равно O(nlogn) Пусть X -- количество сравнений за
14. Среднее время работы Вероятность того, что zi сравнивается с zj равна вероятности того, что в множестве
15. Интроспективная сортировка IntroSort -- быстрая сортировка, которая переключается на пирамидальную по достижении некоторой глубины рекурсии
16. Поиск к-й порядковой статистики за линейное время
17. Нижняя оценка времени работы для сортировок сравнением Теорема: В худшем случае любой алгоритм сортировки сравнениями выполняет
18. Сортировка подсчётом
19. Карманная сортировка Разобьём массив на несколько частей так, чтобы каждая из этих частей была не больше
20. MSD, LSD, Сортировка строк
21. Binary QuickSort
22. Интерполяционный поиск Оптимизация бинпоиска, опирающаяся на то, что ключи распределены равномерно m = l + (r
23. Интерполяционная сортировка
24. Интерполяционная сортировка http://www.ijcte.org/papers/575-A280.pdf
25. Внешние сортировки Позволяют отсортировать массивы данных, которые не могут быть помещены в оперативную память
26. Сортировка многопутевым слиянием Пусть имеем 2Р устройств (внешних файлов) M -- количество данных, которые можем отсортировать
27. Сортировка многопутевым слиянием Производим многопутевое слияние первых блоков с каждого устройства, получая массивы размера M Проводим
28. Сортировка многопутевым слиянием Лемма. Имея P устройств и M оперативной памяти, для сортировки N элементов с
29. Сортировка естественным слиянием Исходный файл разбивается на P-1 файлов по принципу “пока значения элементов возрастают --
30. Сортирующие сети Слой сети -- множество компараторов, имеющих одинаковую глубину Глубина сети -- количество слоёв Размер
31. 0-1 принцип Если сортирующая сеть сортирует любую последовательность из 0 и 1 -- она сортирует все
32. 0-1 принцип Доказательство: Пусть сортирующая сеть сортирует все последовательности 0 и 1, но не сортирует массив
33. Сортирующая сеть Бэтчера Рассмотрим 0-1 битонические последовательности (имеющие вид 0^i1^j0^k или 1^i0^j1^k) Рассмотрим полуфильтр. Если ему
34. Сортирующая сеть Бэтчера Построим объединяющую сеть, которая будет преобразовывать две отсортированные последовательности в две битонические К
35. Сортирующая сеть Бэтчера Глубина сортирующей сети -- O(log^2(n)) Размер сортирующей сети -- O(nlog^2(n))
36. Мастер-теорема Основная теорема об асимптотических оценках устанавливает метод решения рекуррентных соотношений вида T(n) = aT(n/b) +
37. Мастер-теорема
39. Скачать презентацию

Слайд 2

Задача сортировки
Алгоритм сортировки — это алгоритм для упорядочивания элементов в списке.

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

Слайд 3

Характеристики сортировки
Устойчивость -- элементы с равными ключами не меняются местами
Локальная --

не требует дополнительной памяти
Внутренняя/внешняя -- работает с данными в оперативной памяти/с физическими данными
Основанные на операциях сравнения
Адаптивная/неадаптивная -- требуют результатов предыдущих шагов для проведения следующего

Слайд 4

Квадратичные сортировки
Сортировка пузырьком
Сортировка выбором
Сортировка вставками

Слайд 5

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

Слайд 6

Сортировка с помощью кучи

Слайд 7

Слияние К отсортированных массивов с помощью кучи

Слайд 8

TimSort
Массив делится на подмассивы разной длины
Каждый массив сортируется вставками (или другой

устойчивой сортировкой)
Отсортированные подмассивы объединяются с помощью слияния

Слайд 9

TimSort
Выберем значение minrun -- минимального размера подмассива, на которые будет делиться

массив (желательно, чтобы n/minrun было степенью двойки)
Начинаем набирать отсортированные подмассивы:
Если первый элемент не меньше нулевого -- идём, пока элементы неубывают. Иначе -- пока убывают.
Если прошли меньше элементов, чем minrun -- докидываем до minrun и фиксируем
Если элементы в подмассиве упорядочены по убыванию -- инвертируем его

Слайд 10

TimSort
Начинаем процедуру слияния:
Заведём стек пар {Индекс начала подмассива, Размер}
Добавляем очередной подмассив
Пусть

X,Y,Z -- длины последних трёх интервалов.
Пока Z<=X+Y ИЛИ Х>=Y:
Если X>=Y -- сливаем их
Если Z<=X+Y -- сливаем Y с min(X,Z)
Возвращаемся к шагу b
Оптимизация -- галоп:
Если несколько элементов подряд взяли из одного подмассива -- предполагается, что и дальше будем брать из него. Тогда найдём следующий элемент из второго подмассива бинпоиском по первому и скопируем весь первый до него.

Слайд 11

Быстрая сортировка
Массив a[i;j] разбивается на два подмассива a[i;k], a[k+1;j] так, что

для любого x из a[i;k] и для любого y из a[k+1;j] x<=y
Подмассивы сортируются рекурсивно
Объединять не надо, так как между собой подмассивы уже упорядоченны

Слайд 12

Быстрая сортировка
Опорный элемент -- значение ключа, относительно которого разбивается массив на

каждом шаге. Выбор опорного элемента -- первая оптимизация быстрой сортировки:
Случайный элемент из подмассива
Центральный элемент из подмассива
Медиана трёх
При малом размере подмассива его можно отсортировать вставками

Слайд 13

Среднее время работы
Лемма: время работы быстрой сортировки равно O(nlogn)
Пусть X --

количество сравнений за всё время сортировки
Z -- массив, Zij = {z[i], z[j]} -- подмассив
Каждый элемент сравнивается только с опорным, опорный дальше не участвует в сравнении -- то есть максимум любая пара элементов сравнивается один раз

Слайд 14

Среднее время работы
Вероятность того, что zi сравнивается с zj равна вероятности

того, что в множестве Zij опорным элементом выбран либо zi, либо zj
Pr{zi<>zj} = 2/(j-i+1)

Слайд 15

Интроспективная сортировка
IntroSort -- быстрая сортировка, которая переключается на пирамидальную по достижении

некоторой глубины рекурсии

Слайд 16

Поиск к-й порядковой статистики за линейное время

Слайд 17

Нижняя оценка времени работы для сортировок сравнением
Теорема: В худшем случае любой

алгоритм сортировки сравнениями выполняет Ω(nlogn) сравнений, где n — число сортируемых элементов.

Слайд 18

Сортировка подсчётом

Слайд 19

Карманная сортировка
Разобьём массив на несколько частей так, чтобы каждая из этих

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

Слайд 20

MSD, LSD, Сортировка строк

Слайд 21

Binary QuickSort

Слайд 22

Интерполяционный поиск
Оптимизация бинпоиска, опирающаяся на то, что ключи распределены равномерно
m =

l + (r - l) * (x-a[l]) / (a[r] - a[l])
m -- опорный элемент
l, r -- границы подмассива
x -- искомый элемент

Слайд 23

Интерполяционная сортировка

Слайд 24

Интерполяционная сортировка
http://www.ijcte.org/papers/575-A280.pdf

Слайд 25

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

оперативную память

Слайд 26

Сортировка многопутевым слиянием
Пусть имеем 2Р устройств (внешних файлов)
M -- количество данных,

которые можем отсортировать
Изначально все данные в устройстве 0
Считываем первые M данных, сортируем и записываем на устройство P
Так далее, пока не заполним устройства P..2P-1
Если ещё остались данные -- снова сортируем кусок размера M и помещаем в P, P+1 и так далее

Слайд 27

Сортировка многопутевым слиянием
Производим многопутевое слияние первых блоков с каждого устройства, получая

массивы размера M
Проводим несколько таких проходов, чередуя хранилища 0..P-1 и P..2P-1, пока P^iM

Слайд 28

Сортировка многопутевым слиянием
Лемма. Имея P устройств и M оперативной памяти, для

сортировки N элементов с помощью многопутевого слияния потребуется 1+logp(N/M) операций проходов

Слайд 29

Сортировка естественным слиянием
Исходный файл разбивается на P-1 файлов по принципу “пока

значения элементов возрастают -- записываем их в первый файл, если нет -- меняем файл”
Сливаем файлы в один с помощью кучи
Повторяем, пока из всех файлов не получится одна серия

Слайд 30

Сортирующие сети
Слой сети -- множество компараторов, имеющих одинаковую глубину
Глубина сети --

количество слоёв
Размер сети -- количество компараторов

Слайд 31

0-1 принцип
Если сортирующая сеть сортирует любую последовательность из 0 и 1

-- она сортирует все числовые последовательности.
Монотонная функция сохраняет минимум, т.е. f(min(a,b)) = min(f(a), f(b))
Сортировка и монотонная функция коммутируют, то есть неважно, сначала отсортировать массив, а потом применить к каждому элементу монотонную функцию или наоборот.

Слайд 32

0-1 принцип
Доказательство:
Пусть сортирующая сеть сортирует все последовательности 0 и 1, но

не сортирует массив чисел a[0..n-1]. Тогда существует a[i] т.ч. a[i]Построим на массиве a монотонную функцию f т.ч. f(a[j]) = 0, если a[j]<=a[i] и f(a[j]) = 1 иначе
Тогда f(N(a)) == {0000….101….1111}, значит N(f(a)) == {0000….101….1111}
Значит, сортирующая сеть N не сортирует все массивы из 0 и 1

Слайд 33

Сортирующая сеть Бэтчера
Рассмотрим 0-1 битонические последовательности (имеющие вид 0^i1^j0^k или 1^i0^j1^k)
Рассмотрим

полуфильтр. Если ему на вход подать битоническую последовательность -- получим две последовательности -- одну битоническую и одну однородную.
Если применять полуфильтры рекурсивно к получившимся подпоследовательностям -- отсортируем битоническую последовательность

Слайд 34

Сортирующая сеть Бэтчера
Построим объединяющую сеть, которая будет преобразовывать две отсортированные последовательности

в две битонические
К получившимя битоническим последовательностям применим битонический сортировщик
Последовательно применяя такую сеть к подмассивам размера 2,4,8 и так далее, получим сортирующую сеть для N=2^k элементов

Слайд 35

Сортирующая сеть Бэтчера
Глубина сортирующей сети -- O(log^2(n))
Размер сортирующей сети -- O(nlog^2(n))

Слайд 36

Мастер-теорема
Основная теорема об асимптотических оценках устанавливает метод решения рекуррентных соотношений вида T(n)

= aT(n/b) + f(n)

Слайд 37

Лекция 2. Сортировки

Содержание

Задача сортировкиАлгоритм сортировки — это алгоритм для упорядочивания элементов в списке.

Характеристики сортировки Устойчивость -- элементы с равными ключами не меняются местамиЛокальная --

Квадратичные сортировкиСортировка пузырькомСортировка выборомСортировка вставками

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

Сортировка с помощью кучи

Слияние К отсортированных массивов с помощью кучи

TimSortМассив делится на подмассивы разной длиныКаждый массив сортируется вставками (или другой

TimSortВыберем значение minrun -- минимального размера подмассива, на которые будет делиться

TimSortНачинаем процедуру слияния:Заведём стек пар {Индекс начала подмассива, Размер}Добавляем очередной подмассивПусть

Быстрая сортировкаМассив a[i;j] разбивается на два подмассива a[i;k], a[k+1;j] так, что

Быстрая сортировкаОпорный элемент -- значение ключа, относительно которого разбивается массив на

Среднее время работыЛемма: время работы быстрой сортировки равно O(nlogn)Пусть X --

Среднее время работыВероятность того, что zi сравнивается с zj равна вероятности

Интроспективная сортировкаIntroSort -- быстрая сортировка, которая переключается на пирамидальную по достижении

Поиск к-й порядковой статистики за линейное время

Нижняя оценка времени работы для сортировок сравнениемТеорема: В худшем случае любой

Сортировка подсчётом

Карманная сортировкаРазобьём массив на несколько частей так, чтобы каждая из этих

MSD, LSD, Сортировка строк

Binary QuickSort

Интерполяционный поискОптимизация бинпоиска, опирающаяся на то, что ключи распределены равномерноm =

Интерполяционная сортировка

Интерполяционная сортировкаhttp://www.ijcte.org/papers/575-A280.pdf

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

Сортировка многопутевым слияниемПусть имеем 2Р устройств (внешних файлов)M -- количество данных,

Сортировка многопутевым слияниемПроизводим многопутевое слияние первых блоков с каждого устройства, получая

Сортировка многопутевым слияниемЛемма. Имея P устройств и M оперативной памяти, для

Сортировка естественным слияниемИсходный файл разбивается на P-1 файлов по принципу “пока

Сортирующие сетиСлой сети -- множество компараторов, имеющих одинаковую глубинуГлубина сети --

0-1 принципЕсли сортирующая сеть сортирует любую последовательность из 0 и 1

0-1 принципДоказательство:Пусть сортирующая сеть сортирует все последовательности 0 и 1, но

Сортирующая сеть БэтчераРассмотрим 0-1 битонические последовательности (имеющие вид 0^i1^j0^k или 1^i0^j1^k)Рассмотрим

Сортирующая сеть БэтчераПостроим объединяющую сеть, которая будет преобразовывать две отсортированные последовательности

Сортирующая сеть БэтчераГлубина сортирующей сети -- O(log^2(n))Размер сортирующей сети -- O(nlog^2(n))

Мастер-теоремаОсновная теорема об асимптотических оценках устанавливает метод решения рекуррентных соотношений вида T(n)

Мастер-теорема

Похожие презентации