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

1.

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

2.

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

3.

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

4.

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

5.

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

6.

Обратный вызов
Цель. Отсортировать любые типы данных
Как sort() узнает, как сравнивать типы Double, String,
и java.io.File без информации о типе ключа?
Обратный вызов = ссылка на исполняемый код
Клиент посылает массив объектов в функцию
sort()
Функция sort() вызывает метод compareTo() если
нужно

7.

Обратный вызов

8.

Клиент, реализация, интерфейс
Общий порядок для бинарного отношения <=
удовлетворяет:
Несимметрично: если v <= w и w <= v, то v = w
Транзитивно: если v <= w и w <= x, то v <= x
Полнота: v <= w или w <= v или оба
Примеры
Обычный порядок для натуральных и
вещественных чисел
Хронологический порядок для дат
Алфавитный порядок для строк
…

9.

API
Реализовать compareTo() как v.compareTo(w)
Возвращать отрицательное, положительное
целое число или ноль, если v меньше, больше
или равно w
Возвращать исключение, если не сравниваемый
тип (или null)
Встроенные сравниваемые типы: Integer, Double,
String, Date, File, ...

10.

Реализация Comparable
интерфейса
Для Date. Упрощенная версия java.util.Date

11.

Две полезные абстракции
Две полезные функции: сравнение и перестановка
Меньше. Если v меньше w
Перестановка. В массиве a[] поменять местами
объекты с индексами i и j

12.

Проверка
Цель. Проверить отсортирован ли массив

13.

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

14.

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

15.

Сортировка выбором
Алгоритм. Сканирование идет слева направо
Элементы слева от стрелки отсортированы и не
меняются
Нет элемента справа от стрелки, который был бы
меньше элемента слева от стрелки

16.

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

17.

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

18.

Сортировка выбором:
математический анализ
Утверждение. Сортировка выбором использует (N1) + (N-2) + … + 1 + 0 ~ N2/2 сравнений и N
перестановок
Время выполнения не зависит от входных данных.
Квадратичное время, даже если массив

19.

Видео 2

20.

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

21.

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

22.

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

23.

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

24.

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

25.

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

26.

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

27.

Видео 4

28.

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

29.

Видео 5

30.

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

31.

Видео 6

32.

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

33.

Сортировка Шелла: обзор
Идея. Переупорядочить массив так, чтобы каждые
h-е элементы (начиная с любого места в массиве)
составляли упорядоченную последовательность
Сортировка Шелла. [Shell 1959] Независимо
отсортированные чередующиеся
последовательности

34.

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

35.

36.

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

37.

38.

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

39.

40.

Видео 7

41.

Сортировка Шелла: анализ
Утверждение. В худшем случае количество
сравнений при последовательности 3x + 1 равно
O(N3/2)
Точная модель для сортировки Шелла не
разработана.

42.

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

43.

Перетасовка

44.

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

45.

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

46.

Перетасовка Кнута
На итерации i выбрать r между 0 и i при
нормальном распределении
Поменять a[i] и a[r]
Видео 8

47.

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