Дистанционная подготовка к Всероссийской олимпиаде по информатике Преподаватель: к.ф.-м.н., заведующий кафедрой ВТиКГ ДВГУПС Пономарчук Юлия Викторовна. - презентация

1 Дистанционная подготовка к Всероссийской олимпиаде по информатике Преподаватель: к.ф.-м.н., заведующий кафедрой ВТиКГ ДВГУПС Пономарчук Юлия Викторовна

2 Занятие 7. Сортировка

3 Основные сведения Задача сортировки заключается в упорядочивании элементов в заданном списке по невозрастанию – каждый следующий элемент не больше предыдущего или по неубыванию – каждый следующий элемент не меньше предыдущего Обычно сортируются массивы чисел Сортируемые объекты могут быть записями, содержащими несколько полей. Сравнение записей производится по одному из полей – ключу Критерии оценки времени сортировки: 1. Количество шагов, необходимых для упорядочивания N записей 2. Количество сравнений между значениями ключей 3. Если размер записей большой, то необходимо учитывать время, необходимое на перестановку записей

4 Классификация алгоритмов сортировки 1. По устойчивости алгоритмы делятся на устойчивые и неустойчивые. Устойчивая сортировка не меняет взаимного расположения элементов с одинаковыми ключами, неустойчивая – меняет. 2. Алгоритмы делятся на основанные на сравнениях и не основанные на сравнениях. 3. Алгоритмы делятся на алгоритмы внутренней сортировки и внешней сортировки. Внутренняя сортировка оперирует массивами в оперативной памяти. Внешняя сортировка оперирует запоминающими устройствами большого объема с последовательным доступом (файлами).

5 Приложения сортировки 1. Проверка уникальности 2. Удаление повторяющихся элементов 3. Распределение приоритетов событий 4. Поиск порядковой статистики (поиск k-го по величине элемента в массиве) 5. Расчет частоты встречаемости элемента в массиве 6. Восстановление первоначального порядка 7. Создание пересечения или объединения двух массивов 8. Применение бинарного поиска

6 Пузырьковая сортировка O(N 2 ) Идея: На каждом шаге самый «легкий» элемент поднимается до своего места («всплывает»). Для этого просматриваем элементы снизу вверх, берем пару соседних элементов и, если они стоят неправильно, меняем их местами. В лучшем случае, сложность по времени: O(N) Первый проход: Состояние массива после каждого прохода:

7 Пузырьковая сортировка

8 Сортировка прямым выбором O(N 2 ) Идея: Будем выбирать минимальный элемент в оставшейся части массива и приписывать его к уже отсортированной части. Повторив действия N раз, получим отсортированный массив. Количество присваиваний: O(N). В целом: медленный метод, но используется, если необходимо минимизировать количество присваиваний

9 Сортировка прямым выбором

10 Быстрая сортировка O(N*logN) Идея: 1. Для сортировки элементов массива A[1],…,A[n] из этих элементов выбирается некоторое значение v в качестве опорного элемента (желательно посередине). 2. Элементы массива переставляются так, чтобы для некоторого индекса j все переставляемые элементы A[1],…,A[j] имели значения, меньшие чем v, а все элементы A[j+1],…,A[n] – значения, большие или равные v. 3. Процедура быстрой сортировки рекурсивно повторяется к множествам элементов A[1],…,A[j] и A[j+1],…,A[n] для упорядочивания этих множеств по отдельности. Количество присваиваний – O(N*logN). В худшем случае: О(N 2 )

11 Быстрая сортировка

12

13 Поразрядная сортировка Сортировка в соответствии с лексикографическим порядком ключевое значение (a 1, a 2, …, a k ) меньше ключевого значения (b 1, b 2, …, b k ), если существует такой номер j (1 j k-1), что a 1 =b 1, a 2 =b 2, …, a j =b j и a j+1