Файл: Алгоритмы сортировки данных (Алгоритмы устойчивой сортировки).pdf
Добавлен: 28.03.2023
Просмотров: 294
Скачиваний: 2
После сравнения двух элементов наш процесс начинает возвращаться и собирать себя по отсортированным кусочкам массива. В процессе обратного слияния элементы подмассивов сравниваются между собой и в окончательный массив вставляется меньший элемент.
Данный способ означает объединение двух (или более) последовательностей в одну упорядоченную последовательность при помощи циклического выбора элементов, доступных в данный момент.
Сначала задача разбивается на несколько подзадач меньшего размера. Затем эти задачи решаются с помощью рекурсивного вызова или непосредственно, если их размер достаточно мал. Затем их решения комбинируются, и получается решение исходной задачи.
(см. приложение Рисунок 7 Пример)
(см. приложение Рисунок 8 Пример реализации в Java)
1.6 Сортировка с помощью двоичного дерева
Сортировка с помощью двоичного дерева (сортировка двоичным деревом, сортировка деревом, древесная сортировка, сортировка с помощью бинарного дерева, англ. tree sort) — универсальный алгоритм сортировки, заключающийся в построении двоичного дерева поиска по ключам массива (списка), с последующей сборкой результирующего массива путём обхода узлов построенного дерева в необходимом порядке следования ключей. Данная сортировка является оптимальной при получении данных путём непосредственного чтения с потока (например с файла, сокета или консоли).
Алгоритм
1. Построение двоичного дерева.
2. Сборка результирующего массива путём обхода узлов в необходимом порядке следования ключей.
Эффективность
Процедура добавления объекта в бинарное дерево имеет среднюю алгоритмическую сложность порядка O(log(n)). Соответственно, для n объектов сложность будет составлять O(n log(n)), что относит сортировку с помощью двоичного дерева к группе «быстрых сортировок». Однако, сложность добавления объекта в разбалансированное дерево может достигать O(n), что может привести к общей сложности порядка O(n²).
При физическом развёртывании древовидной структуры в памяти требуется не менее чем 4n ячеек дополнительной памяти (каждый узел должен содержать ссылки на элемент исходного массива, на родительский элемент, на левый и правый лист), однако, существуют способы уменьшить требуемую дополнительную память.
Двоичным(бинарным) деревом назовем упорядоченную структуру данных,
в которой каждому элементу - предшественнику или корню (под)дерева -
поставлены в соответствие по крайней мере два других элемента (преемника).
Причем для каждого предшественника выполнено следующее правило:
левый преемник всегда меньше, а правый преемник всегда больше или равен
предшественнику.
Вместо 'предшественник' и 'преемник' также употребляют термины
'родитель' и 'сын'. Все элементы дерева также называют 'узлами'.
При добавлении в дерево нового элемента его последовательно сравнивают
с нижестоящими узлами, таким образом вставляя на место.
Если элемент >= корня - он идет в правое поддерево, сравниваем его уже
с правым сыном, иначе - он идет в левое поддерево, сравниваем с левым,
и так далее, пока есть сыновья, с которыми можно сравнить
Представляет собой универсальный алгоритм сортировки, заключающийся в построении двоичного дерева поиска по ключам массива (списка), с последующей сборкой результирующего массива путём обхода узлов построенного дерева в необходимом порядке следования ключей. Данная сортировка является оптимальной при получении данных путём непосредственного чтения с потока (например из файла, сокета или консоли).
(см. приложение Рисунок 9 Пример)
(см. приложение Рисунок 10 Реализация в Java)
1.7 Сортировка подсчетом
Это сортировка может использоваться только для дискретных данных. Допустим, у нас
есть числа от 0 до 99, которые нам следует отсортировать. Заведем массив размером в 100
элементов, в котором будем запоминать, сколько раз встречалось каждое число (т.е. при
появлении числа будем увеличивать элемент вспомогательного массива с индексом, равным
этому числу, на 1). Затем просто пройдем по всем числам от 0 до 99 и выведем каждое
столько раз, сколько оно встречалось. Сортировка реализуется следующим образом:
for (i=0; i<MAXV; i++)
c[i] = 0;
for (i=0; i<n; i++)
c[a[i]]++;
k=0;
for (i=0; i<MAXV; i++)
for (j=0; j<c[i]; j++)
a[k++]=i;
Здесь MAXV – максимальное значение, которое может встречаться (т.е. все числа
массива должны лежать в пределах от 0 до MAXV-1).
Алгоритм использует O(MAXV) дополнительной памяти и имеет сложность
O(N+MAXV). Его применение дает отличный результат, если MAXV намного меньше, чем
количество элементов в массиве
Сортировка подсчётом - алгоритм сортировки, в котором используется диапазон чисел сортируемого списка для подсчёта совпадающих элементов. Применение сортировки подсчётом целесообразно лишь тогда, когда сортируемые числа имеют (или их можно отобразить в) диапазон возможных значений, который достаточно мал по сравнению с сортируемым множеством, например, миллион натуральных чисел меньших 1000. Простыми словами звучит так: подсчитываем сколько раз в массиве встречается каждое значение и заполняем массив подсчитанными элементами в соответствующих количествах.
(см. приложение Рисунок 11 Реализация в Java)
1.8 Блочная сортировка
Блочная сортировка (Карманная сортировка, корзинная сортировка, англ. Bucket sort) — алгоритм сортировки, в котором сортируемые элементы распределяются между конечным числом отдельных блоков (карманов, корзин) так, чтобы все элементы в каждом следующем по порядку блоке были всегда больше (или меньше), чем в предыдущем. Каждый блок затем сортируется отдельно, либо рекурсивно тем же методом, либо иным другим. Затем элементы помещаются обратно в массив. Этот тип сортировки может обладать линейным временем исполнения.
Данный алгоритм требует знаний о природе сортируемых данных, выходящих за рамки функций "сравнить" и "поменять местами", достаточных для сортировки слиянием, сортировки пирамидой, быстрой сортировки, сортировки Шелла, сортировки вставкой.
Преимущества: относится к классу быстрых алгоритмов с линейным временем исполнения O(N) (на удачных входных данных).
Недостатки: сильно деградирует при большом количестве мало отличных элементов, или же на неудачной функции получения номера корзины по содержимому элемента. В некоторых таких случаях для строк, возникающих в реализациях основанного на сортировке строк алгоритма сжатия BWT, оказывается, что быстрая сортировка строк в версии Седжвика значительно превосходит блочную сортировку скоростью.
АЛГОРИТМ
Если входные элементы подчиняются равномерному закону распределения, то математическое ожидание времени работы алгоритма карманной сортировки является линейным. Это возможно благодаря определенным предположениям о входных данных. При карманной сортировке предполагается, что входные данные равномерно распределены на отрезке [0, 1).
Идея алгоритма заключается в том, чтобы разбить интервал [0, 1) на n одинаковых отрезков (карманов), и разделить по этим карманам n входных величин. Поскольку входные числа равномерно распределены, предполагается, что в каждый карман попадет небольшое количество чисел. Затем последовательно сортируются числа в карманах. Отсортированный массив получается путем последовательного перечисления элементов каждого кармана.
Блочная— алгоритм сортировки, в котором сортируемые элементы распределяются между конечным числом отдельных блоков (карманов, корзин) так, чтобы все элементы в каждом следующем по порядку блоке были всегда больше (или меньше), чем в предыдущем. Каждый блок затем сортируется отдельно, либо рекурсивно тем же методом, либо другим. Затем элементы помещаются обратно в массив. Пример:
(см. приложение Рисунок 12 Элементы распределяются по корзинам)
(см. приложение Рисунок 13 Затем элементы в каждой корзине сортируются)
(см. приложение Рисунок 14 Реализация в C)
1.9 Поразрядная сортировка
Массив несколько раз перебирается и элементы перегруппировываются в зависимости от того, какая цифра находится в определённом разряде. После обработки разрядов (всех или почти всех) массив оказывается упорядоченным.
При этом разряды могут обрабатываться в противоположных направлениях — от младших к старшим или наоборот.
Поразрядная сортировка по младшим разрядам
Элементы перебираются по порядку и группируются по самому младшему разряду (сначала все, заканчивающиеся на 0, затем заканчивающиеся на 1, …, заканчивающиеся на 9). Возникает новая последовательность. Затем группируются по следующему разряду с конца, затем по следующему и т.д. пока не будут перебраны все разряды, от младших к старшим.
Точное название способа LSD radix sort (Least significant digit radix sorts) — поразрядная сортировка по наименьшей значащей цифре.
Поразрядная сортировка по старшим разрядам
Элементы перегруппировываются по определённому разряду (сначала по самому старшему). Затем разбиваются на подгруппы в зависимости от значения этого разряда: равного 0, равного 1, равного 2, …, равного 9. Каждая подгруппа обрабатывается отдельно, в ней к следующему разряду рекурсивно применяется radix sort.
Точное название способа MSD radix sort (Most significant digit radix sorts) — поразрядная сортировка по наибольшей значащей цифре.
MSD реализовывается несколько сложнее, чем LSD, но при этом она эффективнее. При ориентации на наименьшие значащие цифры для всех элементов обрабатываются все разряды. А вот в случае наибольших значащих цифр рекурсия продолжается только до той глубины, до которой это необходимо, то есть пока у элементов подгруппы есть различия в определённом разряде.
Кроме того, MSD, в отличие от LSD, является устойчивым алгоритмом.
Применение поразрядной сортировки имеет одно ограничение: перед началом сортировки необходимо знать
length - максимальное количество разрядов в сортируемых величинах (например, при сортировке слов необходимо знать максимальное количество букв в слове),
range - количество возможных значений одного разряда (при сортировке слов - количество букв в алфавите).
Количество проходов равно числу length.
Пошаговое описание алгоритма
Допустим у нас есть числа: 39, 47, 54, 59, 34, 41, 32 (length = 2, range = 10)
1. Создаем пустые списки, количество которых равно числу range.
2. Распределяем исходные числа по этим спискам в зависимости от величины младшего разряда (по возрастанию).
Для нашего примера получим:
41
32
54, 34
47
59, 39
(Вообще надо создать 10 списков, но некоторые из них оказались пустыми)
3. Собираем числа в той последовательности, в которой они находятся после распределения по спискам.
Получим: 41, 32, 54, 34, 47, 59, 39
4. Повторяем пункты 2 и 3 для всех более старших разрядов поочередно.
Для двузначных чисел мы должны сделать еще один проход. Распределение по спискам будет выглядеть так:
32, 34, 39
41, 47
54, 59
Объединив числа в последовательность, получим отсортированный массив.
(см. приложение Рисунок 15 Реализация в С#)
Глава 2. Алгоритмы неустойчивой сортировки
2.1 Сортировка расческой
Основная идея «расчёски» в том, чтобы первоначально брать достаточно большое расстояние между сравниваемыми элементами и по мере упорядочивания массива сужать это расстояние вплоть до минимального. Таким образом мы как бы причёсываем массив, постепенно разглаживая на всё более аккуратные пряди.
Сортировка расчёской
Первоначальный разрыв между сравниваемыми элементами лучше брать не абы какой, а с учётом специальной величины называемой фактором уменьшения, оптимальное значение которой равно примерно 1,247. Сначала расстояние между элементами равно размеру массива разделённого на фактор уменьшения (результат, естественно, округляется до ближайшего целого). Затем, пройдя массив с этим шагом, мы снова делим шаг на фактор уменьшения и проходим по списку вновь. Так продолжается до тех пор, пока разность индексов не достигнет единицы. В этом случае массив досортировывается обычным пузырьком.
Опытным и теоретическим путём установлено оптимальное значение фактора уменьшения: 1,247330950103979
Когда был изобретён этот метод, на него на стыке 70-х и 80-х мало кто обратил внимание. Десятилетие спустя, когда программирование перестало быть уделом учёных и инженеров IBM, а уже лавинообразно набирало массовый характер, способ переоткрыли, исследовали и популяризировали в 1991 году Стивен Лейси и Ричард Бокс..