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

1.

Элементарные сортировки

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] с каждым большим
элементом слева
Видео 3

16.

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

17.

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

18.

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

19.

Сортировка вставками:
математический анализ


Утверждение. Сортировка вставками использует ~ N 2/4
сравнений и ~ N2/4 перестановок при случайном наборе данных
В среднем каждый ключ проходит половину пути

20.

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

21.

Видео 4

22.

Сортировка вставками: лучший и
худший случай

Лучший случай. Массив отсортирован; необходимо
N-1 сравнений и 0 перестановок
AEELMOPRSTX

Худший случай. Массив отсортирован в обратно
порядке и нет дубликатов; ~ N2/2 сравнений и ~ N2/2
вставок
XTSRPOMLEEA

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]