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

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

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

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

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

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

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

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

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

Быстрая сортировка 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 )

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

Поразрядная сортировка Сортировка в соответствии с лексикографическим порядком ключевое значение (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 <b j+1. Идея: 1. Отсортируем числа по последнему разряду (единиц) 2. Повторим то же самое для второго и последующих разрядов, пользуясь каким-либо устойчивым алгоритмом сортировки Количество присваиваний – O(k*N+k*m), k- количество знаков в числе, m – основание системы счисления.

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

Другие методы сортировки 1. Пирамидальная сортировка O(N*logN) 2. Двоичная сортировка O(N*logN) 3. Сортировка слияниями O(N*logN) 4. Сортировка подсчетом O(N+k) Сравнение производительности алгоритмов сортировок

Сортировка в C++ Библиотека STL: функция sort – сортировка функция stable_sort – устойчивая сортировка функция nth_element – возвращает n-ю порядковую статистику функция unique – удаляет все последовательные дубликаты

Пример. Рейтинг ухажеров У красотки Полли нет недостатка в прекрасно воспитанных ухажер ах. Напротив, самой большой проблемой является отслеживание самых лучших из них. Полли очень любит танцевать, и она считает, что оптимальный рост ее партнера составляет 180 см. Поэтому первое ее требование состоит в том, чтобы найти кого-то, чей рост близок, насколько это возможно, к этой величине. Среди всех кандидатов одного роста ей нужен тот, чей вес близок, насколько это возможно к 75 кг, но не превышает этой величины. Напишите программу, ранжирующую мужчин от более желаемого к менее желаемому. Если у двух или более людей рост и вес совпадают, то отсортируйте их по фамилии, а после, если это необходимо, по имени.