Участник:RandomAtHome/Блочная cортировка: различия между версиями
(Дополнение про сортировку вставками) |
(Закончен математиский параграф 1.2) |
||
| Строка 4: | Строка 4: | ||
== Свойства и структура алгоритмов == | == Свойства и структура алгоритмов == | ||
| − | |||
=== Общее описание алгоритма === | === Общее описание алгоритма === | ||
| Строка 20: | Строка 19: | ||
=== Математическое описание алгоритма === | === Математическое описание алгоритма === | ||
| + | Пусть у нас есть массив из <math>n</math> элементов распределенных равномерно в каком-то неизвестном нам диапазоне и <math>k</math> блоков, по которым мы распределяем эти элементы. | ||
| + | Оценим среднее время работы алгоритма блочной сортировки для случая, при котором в качестве алгоритма сортировки блоков используется сортировка вставками. | ||
| + | |||
| + | Первый шаг - проиницилизировать блоки, найдя наибольший и наименьший элементы. Это возможно сделать за <math>O(n)</math>, за один проход по массиву. Второй шаг, распределение элементов по блокам, вообще говоря, тоже занимает <math>O(n)</math> времени. Так как мы предположили, что внутренней сортировкой является сортировка вставками, то внутренняя сортировка займет <math>O(\textstyle \sum_{i=1}^k \displaystyle n_i^2)</math> времени, где <math>n_i</math> - размер блока с индексом <math>i</math>. | ||
| + | Так как мы считаем среднее время, то надо вычислить математическое ожидание <math>E(n_i^2)</math>. | ||
| + | |||
| + | Введем случайную величину <math>X_{ij}</math>, которая равна <big>1</big>, если <code>A[j]</code> попадает в ''i''-й карман, и <big>0</big> в противном случае. | ||
| + | Очевидно, что <math>n_i = \sum_{j=1}^n X_{ij}</math>. Тогда, | ||
| + | |||
| + | :<math>\begin{align} | ||
| + | E(n_i^2) & = E\left(\sum_{j=1}^n X_{ij} \sum_{k=1}^n X_{ik}\right) \\ | ||
| + | & = E\left(\sum_{j=1}^n \sum_{k=1}^n X_{ij}X_{ik}\right) \\ | ||
| + | & = E\left(\sum_{j=1}^n X_{ij}^2\right) + E\left(\sum_{1\leq j,k\leq n}\sum_{j\neq k}X_{ij}X_{ik}\right) | ||
| + | \end{align} </math> | ||
| + | |||
| + | В последней строчке сумма разделяется на случай <math>j=k</math> и случай <math>j\neq k</math>. Так как вероятность того, что элемент попадет в блок с индексом <math>i</math> равна <math>1/k</math>, <math>X_{ij} </math> равна 1 с вероятностью <math>1/k</math> и равна 0 иначе. | ||
| + | |||
| + | :<math>E(X_{ij}^2) = 1^2\cdot \left(\frac{1}{k}\right) + 0^2\cdot \left(1-\frac{1}{k}\right) = \frac{1}{k}</math> | ||
| + | :<math>E(X_{ij}X_{ik}) = 1\cdot \left(\frac{1}{k}\right)\left(\frac{1}{k}\right) = \frac{1}{k^2} </math> | ||
| + | |||
| + | Подставим эти выражения в сумму и получим: | ||
| + | |||
| + | :<math>E\left(\sum_{j=1}^n X_{ij}^2\right) + E\left(\sum_{1\leq j,k\leq n}\sum_{j\neq k}X_{ij}X_{ik}\right) = n\cdot\frac{1}{k} + n(n-1)\cdot\frac{1}{k^2} = \frac{n^2+nk-n}{k^2}</math> | ||
| + | |||
| + | Следовательно, вычислительная сложность алгоритма равна <math>O\left(\sum_{i=1}^kE(n_i^2)\right) = O\left(\sum_{i=1}^k \frac{n^2+nk-n}{k^2}\right) = O\left(\frac{n^2}{k}+n\right) </math>. | ||
| + | |||
| + | Последний шаг алгоритма, объединение всех блоков в один массив занимает <math>O(k)</math> времени. Следовательно, общая сложность алгоритма равна <math>O\left(n+\frac{n^2}{k}+k\right)</math>. Если k выбрать как некоторую функцию от <math>n</math>, <math>k = \Theta(n)</math>, то вообще говоря среднее время будет равно <math>O(n)</math>, при условии что входные данные равномерно распределены. | ||
| + | |||
=== Вычислительное ядро алгоритма === | === Вычислительное ядро алгоритма === | ||
| Строка 54: | Строка 81: | ||
== Литература == | == Литература == | ||
| + | |||
<references /> | <references /> | ||
Версия 18:12, 24 октября 2019
Требуемые для зачёта пункты описания: 1.1-1.9, 2.4, 2.7, 3.
Общая схема описания алгоритмов имеет следующий вид:
Содержание
- 1 Свойства и структура алгоритмов
- 1.1 Общее описание алгоритма
- 1.2 Математическое описание алгоритма
- 1.3 Вычислительное ядро алгоритма
- 1.4 Макроструктура алгоритма
- 1.5 Схема реализации последовательного алгоритма
- 1.6 Последовательная сложность алгоритма
- 1.7 Информационный граф
- 1.8 Ресурс параллелизма алгоритма
- 1.9 Входные и выходные данные алгоритма
- 1.10 Свойства алгоритма
- 2 Программная реализация алгоритма
- 2.1 Особенности реализации последовательного алгоритма
- 2.2 Локальность данных и вычислений
- 2.3 Возможные способы и особенности параллельной реализации алгоритма
- 2.4 Масштабируемость алгоритма и его реализации
- 2.5 Динамические характеристики и эффективность реализации алгоритма
- 2.6 Выводы для классов архитектур
- 2.7 Существующие реализации алгоритма
- 3 Литература
1 Свойства и структура алгоритмов
1.1 Общее описание алгоритма
Блочная сортировка (Карманная сортировка, корзинная сортировка, англ. Bucket sort) — алгоритм сортировки, в котором сортируемые элементы распределяются между конечным числом отдельных блоков (карманов, корзин) так, чтобы все элементы в каждом следующем по порядку блоке были всегда больше (или меньше), чем в предыдущем. Каждый блок затем сортируется отдельно, либо рекурсивно тем же методом, либо любой другой сортировкой. Затем элементы помещаются обратно в массив. Данный алгоритм требует знаний о природе сортируемых данных, выходящих за рамки функций "сравнить" и "поменять местами", достаточных для большинства других сортировок - например сортировки слиянием, сортировки пирамидой, быстрой сортировки, сортировки Шелла, сортировки вставкой и т.д. В данном случае, дополнительные знания о данных нужны для того, чтобы правильно составить функцию распределяющую элементы по блокам, чтобы количество элементов в каждом блоке было примерно одинаковым.
Особенностью блочной сортировки является то, что она может обладать линейным временем исполнения на удачных входных данных [1], а также очень сильно деградировать на неудачных, в зависимости от алгоритма использующегося внутри блока сортировки. Например, в случае если блок сортируется с помощью сортировки вставками, то сложность становится равной [math]O(n^2)[/math].
Другим интересным примером является случай если число блоков [math]n = 2[/math] и используется рекурсивная блочная сортировка - тогда алгоритм, по сути, становится эквивалентен сортировке Хоара.
Лучше всего алгоритм работает, когда для входных данных удается построить функцию, равномерно распределяющую их по блокам. Хороший пример - набор чисел с фиксированной точкой равномерно распределенный на отрезке [math][0, 1)[/math]. Иными словами, сортировка отлично подходит для случаев когда данные случайны и равномерно распределены по диапазону с известными границах.
Еще стоит отметить, что в алгоритме в качестве внутренней сортировки часто используется сортировка вставками из-за некоторых ее свойств:
- Сортировка вставками может работать по мере поступления данных, в отличие от той же сортировки Хоара или сортировки слиянием
- Из-за константных множителей и членов более низкого порядка сортировка вставками может выполняться для небольших входных данных быстрее, чем другие сортировки с более низким порядком роста[2]
1.2 Математическое описание алгоритма
Пусть у нас есть массив из [math]n[/math] элементов распределенных равномерно в каком-то неизвестном нам диапазоне и [math]k[/math] блоков, по которым мы распределяем эти элементы. Оценим среднее время работы алгоритма блочной сортировки для случая, при котором в качестве алгоритма сортировки блоков используется сортировка вставками.
Первый шаг - проиницилизировать блоки, найдя наибольший и наименьший элементы. Это возможно сделать за [math]O(n)[/math], за один проход по массиву. Второй шаг, распределение элементов по блокам, вообще говоря, тоже занимает [math]O(n)[/math] времени. Так как мы предположили, что внутренней сортировкой является сортировка вставками, то внутренняя сортировка займет [math]O(\textstyle \sum_{i=1}^k \displaystyle n_i^2)[/math] времени, где [math]n_i[/math] - размер блока с индексом [math]i[/math]. Так как мы считаем среднее время, то надо вычислить математическое ожидание [math]E(n_i^2)[/math].
Введем случайную величину [math]X_{ij}[/math], которая равна 1, если A[j] попадает в i-й карман, и 0 в противном случае.
Очевидно, что [math]n_i = \sum_{j=1}^n X_{ij}[/math]. Тогда,
- [math]\begin{align} E(n_i^2) & = E\left(\sum_{j=1}^n X_{ij} \sum_{k=1}^n X_{ik}\right) \\ & = E\left(\sum_{j=1}^n \sum_{k=1}^n X_{ij}X_{ik}\right) \\ & = E\left(\sum_{j=1}^n X_{ij}^2\right) + E\left(\sum_{1\leq j,k\leq n}\sum_{j\neq k}X_{ij}X_{ik}\right) \end{align} [/math]
В последней строчке сумма разделяется на случай [math]j=k[/math] и случай [math]j\neq k[/math]. Так как вероятность того, что элемент попадет в блок с индексом [math]i[/math] равна [math]1/k[/math], [math]X_{ij} [/math] равна 1 с вероятностью [math]1/k[/math] и равна 0 иначе.
- [math]E(X_{ij}^2) = 1^2\cdot \left(\frac{1}{k}\right) + 0^2\cdot \left(1-\frac{1}{k}\right) = \frac{1}{k}[/math]
- [math]E(X_{ij}X_{ik}) = 1\cdot \left(\frac{1}{k}\right)\left(\frac{1}{k}\right) = \frac{1}{k^2} [/math]
Подставим эти выражения в сумму и получим:
- [math]E\left(\sum_{j=1}^n X_{ij}^2\right) + E\left(\sum_{1\leq j,k\leq n}\sum_{j\neq k}X_{ij}X_{ik}\right) = n\cdot\frac{1}{k} + n(n-1)\cdot\frac{1}{k^2} = \frac{n^2+nk-n}{k^2}[/math]
Следовательно, вычислительная сложность алгоритма равна [math]O\left(\sum_{i=1}^kE(n_i^2)\right) = O\left(\sum_{i=1}^k \frac{n^2+nk-n}{k^2}\right) = O\left(\frac{n^2}{k}+n\right) [/math].
Последний шаг алгоритма, объединение всех блоков в один массив занимает [math]O(k)[/math] времени. Следовательно, общая сложность алгоритма равна [math]O\left(n+\frac{n^2}{k}+k\right)[/math]. Если k выбрать как некоторую функцию от [math]n[/math], [math]k = \Theta(n)[/math], то вообще говоря среднее время будет равно [math]O(n)[/math], при условии что входные данные равномерно распределены.
1.3 Вычислительное ядро алгоритма
1.4 Макроструктура алгоритма
1.5 Схема реализации последовательного алгоритма
1.6 Последовательная сложность алгоритма
1.7 Информационный граф
1.8 Ресурс параллелизма алгоритма
1.9 Входные и выходные данные алгоритма
1.10 Свойства алгоритма
2 Программная реализация алгоритма
2.1 Особенности реализации последовательного алгоритма
2.2 Локальность данных и вычислений
2.3 Возможные способы и особенности параллельной реализации алгоритма
2.4 Масштабируемость алгоритма и его реализации
2.5 Динамические характеристики и эффективность реализации алгоритма
2.6 Выводы для классов архитектур
2.7 Существующие реализации алгоритма
3 Литература
- ↑ Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн, Клифорд. Глава 8. Сортировка за линейное время // Алгоритмы: построение и анализ, 2-е издание = Introduction to Algorithms second edition. — М.: «Вильямс», 2005. — С. 230 - 234
- ↑ Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. 2.1. Сортировка вставкой // Алгоритмы: построение и анализ = Introduction to Algorithms / Под ред. И. В. Красикова. — 3-е изд. — М.: Вильямс, 2013. — С. 51.
