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

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

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

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

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

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

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

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

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

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

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

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

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

Видео 2 Видео 2

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

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

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

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

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

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

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

Видео 4 Видео 4

Сортировка вставками: лучший и худший случай Лучший случай. Массив отсортирован; необходимо 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

Видео 5 Видео 5

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

Видео 6 Видео 6

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

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

h-sorting Сортировка вставками через шаг h

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

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

Видео 7 Видео 7

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

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

Перетасовка

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

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

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

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