Элементарные сортировки. Сортировка выбором. Сортировка вставками. Сортировка Шелла. Перетасовка

Август 2, 2022

Главная
Информатика
Элементарные сортировки. Сортировка выбором. Сортировка вставками. Сортировка Шелла. Перетасовка

Содержание

2. Пример: 2-Sum Подсчет количества инструкций, как функции от N.
3. Проблема сортировки Пример. Список студентов Сортировка. Переставить N записей в массиве в определенном порядке
4. Пример сортировки Цель. Отсортировать любые типы данных Пример. Отсортировать случайные вещественные числа в порядке возрастания
5. Пример сортировки Цель. Отсортировать любые типы данных Пример. Отсортировать строки из файла в алфавитном порядке
6. Пример сортировки Цель. Отсортировать любые типы данных Пример. Сортировка файлов в директории по имени
7. Сортировка выбором
8. Сортировка выбором На итерации i найти минимальный оставшийся элемент с индексом min Поменять местами a[i] и
9. Сортировка выбором Алгоритм. Сканирование идет слева направо Элементы слева от стрелки отсортированы и не меняются Нет
10. Сортировка выбором: внутренний цикл
11. Сортировка выбором: реализация на Java
12. Сортировка выбором: математический анализ Утверждение. Сортировка выбором использует (N-1) + (N-2) + … + 1 +
13. Видео 2
14. Сортировка вставками
15. Сортировка вставками На итерации i поменять a[i] с каждым большим элементом слева Видео 3
16. Сортировка вставками Алгоритм. Сканирование идет слева направо Элементы слева от стрелки отсортированы по возрастанию Элементы справа
17. Сортировка вставками: внутренний цикл
18. Сортировка вставками: реализация на Java
19. Сортировка вставками: математический анализ Утверждение. Сортировка вставками использует ~ N2/4 сравнений и ~ N2/4 перестановок при
20. Сортировка вставками: пример
21. Видео 4
22. Сортировка вставками: лучший и худший случай Лучший случай. Массив отсортирован; необходимо N-1 сравнений и 0 перестановок
23. Видео 5
24. Сортировка вставками: частично упорядоченный массив Инверсия — пара элементов, которая нарушает упорядоченность в массиве Частично упорядоченный
25. Видео 6
26. Сортировка Шелла
27. Сортировка Шелла: обзор Идея. Переупорядочить массив так, чтобы каждые h-е элементы (начиная с любого места в
28. h-sorting Сортировка вставками через шаг h Большой шаг => маленькие подмассивы Маленький шаг => массив почти
30. Сортировка Шелла Утверждение. g-отсортированный массив остается g-отсортированным даже после h-сортировки
32. Сортировка Шелла: реализация на Java
34. Видео 7
35. Сортировка Шелла: анализ Утверждение. В худшем случае количество сравнений при последовательности 3x + 1 равно O(N3/2)
36. Чем интересна Сортировка Шелла? Простая идея дает хорошую производительность На практике Работает быстро на небольших массивах
37. Перетасовка
38. Как перетасовать элементы в массиве? Цель. Переставить элементы в массиве так, чтобы они имели равномерное распределение
39. Сортировка Шелла Сгенерировать вещественные числа для каждого элемента Отсортировать массив
40. Перетасовка Кнута На итерации i выбрать r между 0 и i при нормальном распределении Поменять a[i]
41. Перетасовка Кнута На итерации i выбрать r между 0 и i при нормальном распределении Поменять a[i]
45. Скачать презентацию

Слайд 2

Пример: 2-Sum
Подсчет количества инструкций, как функции от N.

Слайд 3

Проблема сортировки
Пример. Список студентов
Сортировка. Переставить N записей в массиве в определенном

порядке

Слайд 4

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

порядке возрастания

Слайд 5

Пример сортировки
Цель. Отсортировать любые типы данных
Пример. Отсортировать строки из файла в

алфавитном порядке

Слайд 6

Пример сортировки
Цель. Отсортировать любые типы данных
Пример. Сортировка файлов в директории по

имени

Слайд 7

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

Слайд 8

Сортировка выбором
На итерации i найти минимальный оставшийся элемент с индексом min
Поменять

местами a[i] и a[min]
Видео 1

Слайд 9

Сортировка выбором
Алгоритм. Сканирование идет слева направо
Элементы слева от стрелки отсортированы и

не меняются
Нет элемента справа от стрелки, который был бы меньше элемента слева от стрелки

Слайд 10

Сортировка выбором: внутренний цикл

Слайд 11

Сортировка выбором: реализация на Java

Слайд 12

Сортировка выбором: математический анализ
Утверждение. Сортировка выбором использует (N-1) + (N-2) +

… + 1 + 0 ~ N2/2 сравнений и N перестановок

Время выполнения не зависит от входных данных. Квадратичное время, даже если массив отсортирован
Перемещение данных минимальное. Перестановки за линейное время

Слайд 13

Видео 2

Слайд 14

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

Слайд 15

Сортировка вставками
На итерации i поменять a[i] с каждым большим элементом слева
Видео

Слайд 16

Сортировка вставками
Алгоритм. Сканирование идет слева направо
Элементы слева от стрелки отсортированы по

возрастанию
Элементы справа от стрелки еще не проверены

Слайд 17

Сортировка вставками: внутренний цикл

Слайд 18

Сортировка вставками: реализация на Java

Слайд 19

Сортировка вставками: математический анализ
Утверждение. Сортировка вставками использует ~ N2/4 сравнений и

~ N2/4 перестановок при случайном наборе данных
В среднем каждый ключ проходит половину пути

Слайд 20

Сортировка вставками: пример

Слайд 21

Видео 4

Слайд 22

Сортировка вставками: лучший и худший случай
Лучший случай. Массив отсортирован; необходимо N-1

сравнений и 0 перестановок
A E E L M O P R S T X
Худший случай. Массив отсортирован в обратно порядке и нет дубликатов; ~ N2/2 сравнений и ~ N2/2 вставок
X T S R P O M L E E A

Слайд 23

Видео 5

Слайд 24

Сортировка вставками: частично упорядоченный массив
Инверсия — пара элементов, которая нарушает упорядоченность

в массиве

Частично упорядоченный массив — массив, в котором количество инверсий <= cN
Массив, каждый элемент которого находится неподалеку от своей окончательной позиции
Небольшой массив, добавленный к большому отсортированному массиву
Массив, в котором лишь несколько элементов находятся не на своем месте
Для частично упорядоченного массива сортировка вставками выполняется за линейное время
Количество перестановок равно количеству инверсий

Слайд 25

Видео 6

Слайд 26

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

Слайд 27

Сортировка Шелла: обзор
Идея. Переупорядочить массив так, чтобы каждые h-е элементы (начиная

с любого места в массиве) составляли упорядоченную последовательность

Сортировка Шелла. [Shell 1959] Независимо отсортированные чередующиеся последовательности

Слайд 28

h-sorting
Сортировка вставками через шаг h
Большой шаг => маленькие подмассивы
Маленький шаг =>

массив почти упорядочен

Слайд 29

Слайд 30

Сортировка Шелла
Утверждение. g-отсортированный массив остается g-отсортированным даже после h-сортировки

Слайд 31

Слайд 32

Сортировка Шелла: реализация на Java

Слайд 33

Слайд 34

Видео 7

Слайд 35

Сортировка Шелла: анализ
Утверждение. В худшем случае количество сравнений при последовательности 3x

+ 1 равно O(N3/2)

Точная модель для сортировки Шелла не разработана.

Слайд 36

Чем интересна Сортировка Шелла?
Простая идея дает хорошую производительность
На практике
Работает быстро на

небольших массивах (bzip2/linux kernel)
Проста в реализации и используется во встраиваемых системах
Есть аппаратные реализации
Простой алгоритм, нетривиальная производительность
Асимптотический порядок роста?
Лучшая последовательность?
Производительность в среднем случае?
Некоторые замечательные алгоритмы ждут исследования

Слайд 37

Перетасовка

Слайд 38

Как перетасовать элементы в массиве?
Цель. Переставить элементы в массиве так, чтобы

они имели равномерное распределение

Слайд 39

Сортировка Шелла
Сгенерировать вещественные числа для каждого элемента
Отсортировать массив

Слайд 40

Перетасовка Кнута
На итерации i выбрать r между 0 и i при

нормальном распределении
Поменять a[i] и a[r]
Видео 8

Слайд 41

Перетасовка Кнута
На итерации i выбрать r между 0 и i при

нормальном распределении
Поменять a[i] и a[r]

Слайд 42

Слайд 43

Элементарные сортировки. Сортировка выбором. Сортировка вставками. Сортировка Шелла. Перетасовка

Содержание

Пример: 2-SumПодсчет количества инструкций, как функции от N.

Проблема сортировкиПример. Список студентовСортировка. Переставить N записей в массиве в определенном

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

Пример сортировкиЦель. Отсортировать любые типы данныхПример. Отсортировать строки из файла в

Пример сортировкиЦель. Отсортировать любые типы данныхПример. Сортировка файлов в директории по

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

Сортировка выборомНа итерации i найти минимальный оставшийся элемент с индексом minПоменять

Сортировка выборомАлгоритм. Сканирование идет слева направоЭлементы слева от стрелки отсортированы и

Сортировка выбором: внутренний цикл

Сортировка выбором: реализация на Java

Сортировка выбором: математический анализУтверждение. Сортировка выбором использует (N-1) + (N-2) +

Видео 2

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

Сортировка вставкамиНа итерации i поменять a[i] с каждым большим элементом слеваВидео

Сортировка вставкамиАлгоритм. Сканирование идет слева направоЭлементы слева от стрелки отсортированы по

Сортировка вставками: внутренний цикл

Сортировка вставками: реализация на Java

Сортировка вставками: математический анализУтверждение. Сортировка вставками использует ~ N2/4 сравнений и

Сортировка вставками: пример

Видео 4

Сортировка вставками: лучший и худший случайЛучший случай. Массив отсортирован; необходимо N-1

Видео 5

Сортировка вставками: частично упорядоченный массивИнверсия — пара элементов, которая нарушает упорядоченность

Видео 6

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

Сортировка Шелла: обзорИдея. Переупорядочить массив так, чтобы каждые h-е элементы (начиная

h-sortingСортировка вставками через шаг hБольшой шаг => маленькие подмассивыМаленький шаг =>

Сортировка ШеллаУтверждение. g-отсортированный массив остается g-отсортированным даже после h-сортировки

Сортировка Шелла: реализация на Java

Видео 7

Сортировка Шелла: анализУтверждение. В худшем случае количество сравнений при последовательности 3x

Чем интересна Сортировка Шелла?Простая идея дает хорошую производительностьНа практикеРаботает быстро на

Перетасовка

Как перетасовать элементы в массиве?Цель. Переставить элементы в массиве так, чтобы

Сортировка ШеллаСгенерировать вещественные числа для каждого элементаОтсортировать массив

Перетасовка КнутаНа итерации i выбрать r между 0 и i при

Перетасовка КнутаНа итерации i выбрать r между 0 и i при

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

Пример: 2-Sum
Подсчет количества инструкций, как функции от N.

Проблема сортировки
Пример. Список студентов
Сортировка. Переставить N записей в массиве в определенном

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

Пример сортировки
Цель. Отсортировать любые типы данных
Пример. Отсортировать строки из файла в

Пример сортировки
Цель. Отсортировать любые типы данных
Пример. Сортировка файлов в директории по

Сортировка выбором
На итерации i найти минимальный оставшийся элемент с индексом min
Поменять

Сортировка выбором
Алгоритм. Сканирование идет слева направо
Элементы слева от стрелки отсортированы и

Сортировка выбором: математический анализ
Утверждение. Сортировка выбором использует (N-1) + (N-2) +

Сортировка вставками
На итерации i поменять a[i] с каждым большим элементом слева
Видео

Сортировка вставками
Алгоритм. Сканирование идет слева направо
Элементы слева от стрелки отсортированы по

Сортировка вставками: математический анализ
Утверждение. Сортировка вставками использует ~ N2/4 сравнений и

Сортировка вставками: лучший и худший случай
Лучший случай. Массив отсортирован; необходимо N-1

Сортировка вставками: частично упорядоченный массив
Инверсия — пара элементов, которая нарушает упорядоченность

Сортировка Шелла: обзор
Идея. Переупорядочить массив так, чтобы каждые h-е элементы (начиная

h-sorting
Сортировка вставками через шаг h
Большой шаг => маленькие подмассивы
Маленький шаг =>

Сортировка Шелла
Утверждение. g-отсортированный массив остается g-отсортированным даже после h-сортировки

Сортировка Шелла: анализ
Утверждение. В худшем случае количество сравнений при последовательности 3x

Чем интересна Сортировка Шелла?
Простая идея дает хорошую производительность
На практике
Работает быстро на

Как перетасовать элементы в массиве?
Цель. Переставить элементы в массиве так, чтобы

Сортировка Шелла
Сгенерировать вещественные числа для каждого элемента
Отсортировать массив

Перетасовка Кнута
На итерации i выбрать r между 0 и i при

Перетасовка Кнута
На итерации i выбрать r между 0 и i при