|
|
Лекция 3 Блок 1 Задача о сортировке Блок 2 Теорема о сортировках сравнения Блок 3
МЕТОДЫ ПРОГРАММИРОВАНИЯ3 КУРС КБ 1-Й СЕМЕСТР Лекция 3
Блок 1
Блок 2
- Теорема о сортировках сравнения
Блок 3
Блок 4
Блок 1 - Задача о сортировке
- Виды сортировок
Задача о сортировке
Имеется одномерный массив чисел, состоящий из n элементов: X[n].
Переставить элементы массива так, чтобы их значения располагались в порядке возрастания. Другими словами, для любой пары элементов X[i] и X[i+1] выполняется неравенство вида:
X[i] <= X[i+1].
Алгоритмы сортировки
Сортировка пузырьком / Bubble sort : O(n2), в лучшем случае – O(n)
Шейкерная сортировка / Shaker sort
Сортировка расческой / Comb sort: O(nlogn), в худшем – O(n2)
Сортировка вставками / Insertion sort : в среднем и худшем случае – O(n2), в лучшем – O(n).
Сортировка Шелла / Shellsort : O(n2).
Сортировка деревом / Tree sort : O(nlogn) в худшем, среднем и лучшем случае.
Гномья сортировка / Gnome sort : Алгоритм похож на сортировку вставками.
Сортировка выбором / Selection sort : O(n2) в лучшем, среднем и худшем случае.
Пирамидальная сортировка / Heapsort: O(nlogn) в худшем, среднем и лучшем случае.
Быстрая сортировка / Quicksort : O(nlogn) в среднем и лучшем случае, O(n2) – в худшем
Сортировка слиянием / Merge sort : O(n log n).
Сортировка подсчетом / Counting sort : O(n + max_el — min_el).
Блочная сортировка / Bucket sort. (также известна как корзинная и карманная сортировка)
Поразрядная сортировка / Radix sort
LSD (least significant digit): O(n)
MSD (most significant digit): разновидность блочной сортировки.
Би-тонная сортировка / Bitonic sort O(nlog2n)
Timsort - Гибридная сортировка, совмещающая сортировку вставками и сортировку слиянием. O(n) в лучшем случае и O(n log n) в среднем и худшем случае.
Время работы Время работы - Эту классификацию обычно считают самой важной. Оценивают худшее время алгоритма, среднее и лучшее. Лучшее время — минимальное время работы алгоритма на каком-либо наборе, обычно этим набором является тривиальный [1…n]. Худшее время — наибольшее время. У большинства алгоритмов временные оценки бывают O(nlogn) и O(n2).
Память - Параметр сортировки, показывающий, сколько дополнительной памяти требуется алгоритму. Сюда входят и дополнительный массив, и переменные, и затраты на стек вызовов. Обычно затраты бывают O(1), O(logn), O(n).
Устойчивость - Устойчивой сортировкой называется сортировка, не меняющая порядка объектов с одинаковыми ключами. Ключ — поле элемента, по которому мы производим сортировку.
Количество обменов - Количество обменов может быть важным параметром в случае, если объекты имеют большой размер. В таком случае при большом количестве обменов время алгоритма заметно увеличивается.
Детерминированность - Алгоритм сортировки называется детерминированным, если каждая операция присваивания, обмена и т.д. не зависит от предыдущих. Все сортирующие сети являются детерминированными.
Название
|
Лучшее время
|
Среднее
|
Худшее
|
Память
|
Устойчивость
|
Обмены (в среднем)
|
Описание
|
Сортировка пузырьком(Bubble Sort)
|
O(n)
|
O(n2)
|
O(n2)
|
O(1)
|
Да
|
O(n2)
|
Алгоритм состоит в повторяющихся проходах по сортируемому массиву. На каждой итерации последовательно сравниваются соседние элементы, и, если порядок в паре неверный, то элементы меняют местами.
|
Сортировка вставками(Insertion Sort)
|
O(n)
|
O(n2)
|
O(n2)
|
O(1)
|
Да
|
O(n2)
|
На каждом шаге алгоритма мы выбираем один из элементов входных данных и вставляем его на нужную позицию в уже отсортированной части массива до тех пор, пока весь набор входных данных не будет отсортирован.
|
Сортировка Шелла(Shellsort)
|
O(nlog2n)
|
Зависит от выбора шага
|
O(n2)
|
O(1)
|
Нет
|
O(n2)
|
Является модификацией сортировки вставками, сортируем между собой элементы, стоящие на кратных нашему шагу местах.
|
Сортировка выбором(Selection Sort)
|
O(n2)
|
O(n2)
|
O(n2)
|
O(1)
|
Нет
|
O(n)
|
На i-ом шаге алгоритма находим минимальный среди последних n−i+1, и меняем его местами с i-ым элементом в массиве.
|
Быстрая сортировка(Quick Sort)
|
O(nlogn)
|
O(nlogn)
|
O(n2)) (маловероятно)
|
O(logn)) (стек вызовов)
|
Нет
|
O(nlogn)
|
Один из самых известных и широко используемых алгоритмов сортировки. Алгоритм состоит в выборе опорного элемента, разделении массива на 2 части относительно опорного (одна — все элементы, меньшие опорного элемента, вторая — большие), и в сортировке полученных частей рекурсивным вызовом себя от них.
|
Сортировка слиянием(Merge Sort)
|
O(nlogn)
|
O(nlogn)
|
O(nlogn)
|
O(n) (обычная реализация) O(1) (модифицированная реализация)
|
Да
|
O(nlogn)
|
Алгоритм состоит в разделении массива пополам, сортировке половин и их слиянии.
|
Timsort
|
O(n)
|
O(nlogn)
|
O(nlogn)
|
O(n)
|
Да
|
O(nlogn)
|
Гибрид сортировки слиянием. Разбиваем массив на подмассивы фиксированной длины и сортируем каждый подмассив любой устойчивой сортировкой. После чего объединяем отсортированные подмассивы модифицированной сортировкой слиянием.
|
Сортировка кучей(Heap Sort)
|
O(nlogn)
|
O(nlogn)
|
O(nlogn)
|
O(1)
|
Нет
|
O(nlogn)
|
Строим из массива кучу, по очереди извлекаем минимум кучи.
|
Плавная сортировка(Smoothsort)
|
O(n)
|
O(nlogn)
|
O(nlogn)
|
O(1)
|
Нет
|
O(nlogn)
|
Модификация сортировки кучей. Вместо двоичной кучи используем K-ую кучу Леонардо.
|
Терпеливая сортировка(Patience sorting)
|
O(nlogn)
|
O(nlogn)
|
O(nlogn)
|
O(n)
|
Нет
|
O(nlogn)
|
Раскидываем элементы массива по стопкам, после чего строим двоичную кучу из стопок. Позволяет также вычислить длину наибольшей возрастающей подпоследовательности данного массива.
|
Сортировка с помощью бинарного дерева(Tree Sort)
|
O(n)
|
O(nlogn)
|
O(nlogn)
|
O(n)
|
Да
|
O(n)
|
Добавляем по очереди вершины в сбалансированное дерево поиска, проходим по всем вершинам в порядке возрастания.
|
Карманная сортировка(Bucket Sort)
|
O(n+k)
|
O(nlogkn)
|
O(n⋅k)
|
O(n)
|
Да
|
-
|
Распределяем элементы в k карманов, сортируем элементы внутри карманов, из каждого кармана данные записываются в массив в порядке разбиения.
|
Цифровая сортировка(Radix Sort)
|
O(nlogn)
|
O(nlogn)O
|
O(nlogn)
|
O(n)
|
Да
|
-
|
Сортировка объектов равной длины, имеющих "разряды". обычно это строки или целые числа. Алгоритм состоит в том, чтобы отсортировать объекты по разрядам, начиная от младших к старшим.
|
Сортировка подсчетом(Counting Sort)
|
O(n)
|
O(n+k)
|
O(k)
|
O(k)
|
Да
|
O(n+k)
|
Сортировка целых чисел, входящих в какой-то небольшой диапазон. Создаем массив длины диапазона k, каждый элемент которого будет показывать, сколько исходных элементов равны данному. Бежим по массиву и считаем количество вхождений каждого числа.
|
Сортировка Хэна(Han's Sort)
|
O(nloglogn)
|
O(nloglogn)
|
O(nloglogn)
|
O(n)
|
Да
|
O(nloglogn)
|
Очень сложная сортировка, основанная на принадлежности ключей к целым числам. Использует экспоненциальное поисковое дерево Андерсона.
|
Многопоточная сортировка слиянием(Multithreaded merge sort)
| | | |
O(n)
|
Да
|
O(nlogn)
|
Отличается от сортировки слиянием только тем, что при рекурсивном вызове будет создавать новый поток.
|
PSRS-сортировка(PSRS-sorting)
| | | | |
Нет
|
O(nlogn)
|
Разделим массив на Nind подмассива и запустим в каждой быструю сортировку. После этого объединим все эти подмассивы.
|
Сортировка подсчетом(Counting Sort)
|
O(n)
|
O(n+k)
|
O(k)
|
O(k)
|
Да
|
O(n+k)
|
Сортировка целых чисел, входящих в какой-то небольшой диапазон. Создаем массив длины диапазона k, каждый элемент которого будет показывать, сколько исходных элементов равны данному. Бежим по массиву и считаем количество вхождений каждого числа.
|
Сортировка Хэна(Han's Sort)
|
O(nloglogn)
|
O(nloglogn)
|
O(nloglogn)
|
O(n)
|
Да
|
O(nloglogn)
|
Очень сложная сортировка, основанная на принадлежности ключей к целым числам. Использует экспоненциальное поисковое дерево Андерсона.
|
Многопоточная сортировка слиянием(Multithreaded merge sort)
| | | |
O(n)
|
Да
|
O(nlogn)
|
Отличается от сортировки слиянием только тем, что при рекурсивном вызове будет создавать новый поток.
|
PSRS-сортировка(PSRS-sorting)
| | | | |
Нет
|
O(nlogn)
|
Разделим массив на Nind подмассива и запустим в каждой быструю сортировку. После этого объединим все эти подмассивы.
| Блок 2 - Теорема о нижней оценке числа сравнений для сортировок сравнениями
Теорема
В худшем случае любой алгоритм сортировки сравнениями выполняет Ω(n log(n)) сравнений, где n — число сортируемых элементов.
Доказательство Надо доказать высота такого дерева для любого алгоритма сортировки сравнениями не меньше чем Ω(nlogn), где n — количество элементов.
Ограничимся рассмотрением сортировки перестановок n элементов. При сравнении некоторых двух из них, существует два возможных исхода (ai⩽aj и ai>aj), значит, каждый узел дерева имеет не более двух сыновей.
Всего существует n! различных перестановок n элементов, значит, число листьев нашего дерева не менее n! (в противном случае некоторые перестановки были бы не достижимы из корня, а, значит, алгоритм не правильно работал бы на некоторых исходных данных).
Блок 3 Сортировка слиянием (англ. Merge sort) - Алгоритм использует принцип «разделяй и властвуй»: задача разбивается на подзадачи меньшего размера, которые решаются по отдельности, после чего их решения комбинируются для получения решения исходной задачи.
- Если в рассматриваемом массиве один элемент, то он уже отсортирован — алгоритм завершает работу.
- Иначе массив разбивается на две части, которые сортируются рекурсивно.
- После сортировки двух частей массива к ним применяется процедура слияния, которая по двум отсортированным частям получает исходный отсортированный массив.
Процедура слияния - Массив разбиваем на 2 части a и b.
- Нам надо получить массив c размером |a|+|b|.
- процедуру слияния.
- мы сравниваем элементы массивов (начиная с начала) и меньший из них записываем в финальный.
- в массиве у которого оказался меньший элемент, переходим к следующему элементу и сравниваем теперь его.
- в конце, если один из массивов закончился, мы просто дописываем в финальный другой массив. После мы наш финальный массив записываем заместо двух исходных и получаем отсортированный участок.
Множество отсортированных списков с операцией merge является моноидом, где нейтральным элементом будет пустой список. Псевдокод процедуры слияния, который сливает две части массива a — [left;mid) и [mid;right) Рекурсивная реализация
сортировка подотрезка массива с индексами в полуинтервале [left;right)
Итеративная реализация Время работы Время работы - Чтобы оценить время работы этого алгоритма, составим рекуррентное соотношение. Пусть T(n) — время сортировки массива длины n, тогда для сортировки слиянием справедливо T(n)=2T(n/2)+O(n)
- O(n) — время, необходимое на то, чтобы слить два массива длины n. Распишем это соотношение:
- T(n)=2T(n/2)+O(n)=4T(n/4)+2O(n)=⋯=T(1)+log(n)O(n)=O(nlog(n)).
Сравнение с другими алгоритмами - Достоинства:
- устойчивая,
- можно написать эффективную многопоточную сортировку слиянием,
- сортировка данных, расположенных на периферийных устройствах и не вмещающихся в оперативную память.
- Недостатки:
- требуется дополнительно O(n) памяти, но можно модифицировать до O(1).
Блок 4 - Общий вид быстрой сортировки.
- Варианты выбора опорного элемента.
- Операция partition.
- Анализ времени работы и используемой памяти.
Quicksort
Быстрая сортировка, сортировка Хоара (англ. quicksort), часто называемая qsort (по имени в стандартной библиотеке языка Си) — алгоритм сортировки, разработанный английским информатиком Тони Хоаром во время своей работы в МГУ в 1960 году.
Один из самых быстрых известных универсальных алгоритмов сортировки массивов: в среднем O(nlog n) обменов при упорядочении n элементов; из-за наличия ряда недостатков на практике обычно используется с некоторыми доработками.
Алгоритм
Массив делится на подмассивы путем выбора опорного (pivot) элемента (элемента, выбранного из массива).
При разделении массива опорный элемент должен располагаться таким образом, чтобы элементы меньше опорного оставались с левой стороны, а элементы больше поворота находились с правой стороны от поворота.
Левый и правый подмассивы также разделяются с использованием того же подхода. Этот процесс продолжается до тех пор, пока каждый подмассив не будет содержать единственный элемент.
На этом этапе элементы уже отсортированы. Наконец, элементы объединяются в отсортированный массив.
Массив a[l…r] типа T разбивается на два (возможно пустых) подмассива a[l…q] и a[q+1…r], таких, что каждый элемент a[l…q] меньше или равен a[q], который в свою очередь, не превышает любой элемент подмассива a[q+1…r]. Индекс вычисляется в ходе процедуры разбиения.
Подмассивы a[l…q] и a[q+1…r] сортируются с помощью рекурсивного вызова процедуры быстрой сортировки.
Поскольку подмассивы сортируются на месте, для их объединения не требуются никакие действия: весь массив a[l…r] оказывается отсортированным.
1. Select the Pivot Element
- Существуют различные варианты быстрой сортировки, в которых элемент поворота выбирается из разных позиций.
- Здесь мы выберем крайний правый элемент массива в качестве опорного элемента.
2. Rearrange the Array
- Теперь элементы массива переставлены так, что элементы, которые меньше, чем опорный элемент, помещаются слева, а элементы, превышающие точку поворота, помещаются справа.
Если достигается элемент, меньший, чем опорный элемент , меньший элемент заменяется более крупным элементом, найденным ранее. И замените его другим меньшим элементом.
3. Divide Subarrays
- Элементы поворота снова выбираются отдельно для левой и правой частей. И шаг 2 повторяется.
Псевдокод
Еще псевдокод
Для сортировки всего массива необходимо выполнить процедуру quicksort(a,0,length[a]−1).
Еще псевдокод Сложность Quicksort
Временная сложность
|
|
Лучшая
|
O(n*log n)
|
Худшая
|
O(n2)
|
Средняя
|
O(n*log n)
|
Space Complexity
|
O(log n)
|
Стабильность
|
No
|
Первые два члена относятся к двум рекурсивным вызовам, последний термин - к процессу разделения. k - количество элементов, меньших, чем pivot.
Худшая сложность
Это условие приводит к тому, что опорный элемент находится на крайнем конце отсортированного массива. Один подмассив всегда пуст, а другой подмассив содержит n - 1 элемент. Таким образом, быстрая сортировка вызывается только для этого подмассива.
Это происходит, когда выбранный опорный элемент является либо самым большим, либо самым маленьким элементом.
Средняя сложность
Это происходит, когда опорный элемент всегда является средним элементом или рядом с ним.
До следующей лекции… |
|
|
Скачать 3.75 Mb.