Участник:RandomAtHome/Блочная cортировка: различия между версиями

Версия 16:56, 24 октября 2019

Требуемые для зачёта пункты описания: 1.1-1.9, 2.4, 2.7, 3.

Общая схема описания алгоритмов имеет следующий вид:

Содержание

1 Свойства и структура алгоритмов
2 Программная реализация алгоритма
3 Литература

1 Свойства и структура алгоритмов

Свойства алгоритмов никак не зависят от вычислительных систем, и с этой точки зрения данная часть AlgoWiki имеет безусловную собственную ценность. Описание алгоритма делается один раз, после чего многократно используется для его реализации в различных программно-аппаратных средах. Несмотря на то, что в данной части мы рассматриваем лишь машинно-независимые свойства алгоритмов, соображения, важные на этапе реализации, или же ссылки на соответствующие пункты части II AlgoWiki, здесь также вполне уместны.

1.1 Общее описание алгоритма

Блочная сортировка (Карманная сортировка, корзинная сортировка, англ. Bucket sort) — алгоритм сортировки, в котором сортируемые элементы распределяются между конечным числом отдельных блоков (карманов, корзин) так, чтобы все элементы в каждом следующем по порядку блоке были всегда больше (или меньше), чем в предыдущем. Каждый блок затем сортируется отдельно, либо рекурсивно тем же методом, либо любой другой сортировкой. Затем элементы помещаются обратно в массив. Данный алгоритм требует знаний о природе сортируемых данных, выходящих за рамки функций "сравнить" и "поменять местами", достаточных для большинства других сортировок - например сортировки слиянием, сортировки пирамидой, быстрой сортировки, сортировки Шелла, сортировки вставкой и т.д. В данном случае, дополнительные знания о данных нужны для того, чтобы правильно составить функцию распределяющую элементы по блокам, чтобы количество элементов в каждом блоке было примерно одинаковым.

Особенностью блочной сортировки является то, что она может обладать линейным временем исполнения на удачных входных данных ^[1], а также очень сильно деградировать на неудачных, в зависимости от алгоритма использующегося внутри блока сортировки. Например, в случае если блок сортируется с помощью сортировки вставками, то сложность становится равной [math]O(n^2)[/math].

Другим интересным примером является случай если число блоков [math]n = 2[/math] и используется рекурсивная блочная сортировка - тогда алгоритм, по сути, становится эквивалентен сортировке Хоара.

Лучше всего алгоритм работает, когда для входных данных удается построить функцию, равномерно распределяющую их по блокам. Хороший пример - набор чисел с фиксированной точкой равномерно распределенный на отрезке [math][0, 1)[/math]. Иными словами, сортировка отлично подходит для случаев когда данные случайны и равномерно распределены по диапазону с известными границах.

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 Литература

↑ Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн, Клифорд. Глава 8. Сортировка за линейное время // Алгоритмы: построение и анализ, 2-е издание = Introduction to Algorithms second edition. — М.: «Вильямс», 2005. — С. 230 - 234

[ref1-1] Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн, Клифорд. Глава 8. Сортировка за линейное время // Алгоритмы: построение и анализ, 2-е издание = Introduction to Algorithms second edition. — М.: «Вильямс», 2005. — С. 230 - 234

[1]

@@ Строка 7: / Строка 7: @@
 === Общее описание алгоритма ===
-В данном разделе представляется самый первый вариант описания тех задач (или классов задач), для решения которых предназначен алгоритм. В описании поясняются особенности как алгоритма, так и объектов, с которыми он работает. Если описание соответствует целому классу схожих по структуре алгоритмов, либо же посвящено описанию отдельного представителя некоторого класса, то это здесь указывается явно. Описываются базовые математические свойства и структура входных данных. При необходимости, в описании могут присутствовать формулы, а также даваться ссылки на описания других используемых алгоритмов. Данное описание должно быть достаточным для однозначного понимания сути решаемой задачи.
+Блочная сортировка (Карманная сортировка, корзинная сортировка, англ. Bucket sort) — алгоритм сортировки, в котором сортируемые элементы распределяются между конечным числом отдельных блоков (карманов, корзин) так, чтобы все элементы в каждом следующем по порядку блоке были всегда больше (или меньше), чем в предыдущем. Каждый блок затем сортируется отдельно, либо рекурсивно тем же методом, либо любой другой сортировкой. Затем элементы помещаются обратно в массив. Данный алгоритм требует знаний о природе сортируемых данных, выходящих за рамки функций "сравнить" и "поменять местами", достаточных для большинства других сортировок - например сортировки слиянием, сортировки пирамидой, быстрой сортировки, сортировки Шелла, сортировки вставкой и т.д. В данном случае, дополнительные знания о данных нужны для того, чтобы правильно составить функцию распределяющую элементы по блокам, чтобы количество элементов в каждом блоке было примерно одинаковым.
+Особенностью блочной сортировки является то, что она может обладать линейным временем исполнения на удачных входных данных <ref name="ref1">Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн, Клифорд. Глава 8. Сортировка за линейное время // Алгоритмы: построение и анализ, 2-е издание = Introduction to Algorithms second edition. — М.: «Вильямс», 2005. — С. 230 - 234</ref>, а также очень сильно деградировать на неудачных, в зависимости от алгоритма использующегося внутри блока сортировки. Например, в случае если блок сортируется с помощью сортировки вставками, то сложность становится равной <math>O(n^2)</math>.
+Другим интересным примером является случай если число блоков <math>n = 2</math> и используется рекурсивная блочная сортировка - тогда алгоритм, по сути, становится эквивалентен сортировке Хоара.
+Лучше всего алгоритм работает, когда для входных данных удается построить функцию, равномерно распределяющую их по блокам. Хороший пример - набор чисел с фиксированной точкой равномерно распределенный на отрезке <math>[0, 1)</math>. Иными словами, сортировка отлично подходит для случаев когда данные случайны и равномерно распределены по диапазону с известными границах.
 === Математическое описание алгоритма ===
-Приводится математическое описание решаемой задачи в виде совокупности формул и соотношений, как это принято в книгах и учебниках. По возможности, используются общепринятые обозначения и способы записи. Должны быть явно определены все использованные обозначения и описаны свойства входных данных. Представленное описание должно быть достаточным для однозначного понимания постановки решаемой задачи для человека, знающего математику.
+Дадим оценку
 === Вычислительное ядро алгоритма ===