Сортировка библиотеки
 | Эта статья нуждается в дополнительных цитатах для проверки . ( октябрь 2017 г. ) |
| Сорт | Алгоритм сортировки |
|---|---|
| Структура данных | Множество |
| Худшая производительность | |
| Лучшая производительность | |
| Средняя производительность | |
| Наихудшая пространственная сложность | |
| Оптимальный | ? |
Библиотечная сортировка или сортировка вставкой с пробелами — это алгоритм сортировки , который использует сортировку вставкой , но с пробелами в массиве для ускорения последующих вставок. Название происходит от аналогии:
Предположим, библиотекарь должен был хранить свои книги в алфавитном порядке на длинной полке, начиная с буквы «А» на левом конце и продолжая вправо вдоль полки без промежутков между книгами до конца буквы «З». Если библиотекарь приобрел новую книгу, принадлежащую разделу B, то как только он найдет подходящее место в разделе B, ему придется переместить каждую книгу, от середины B до Z, чтобы освободи место для новой книги. Это сортировка вставками. Однако если бы им пришлось оставлять пробел после каждой буквы, пока после B еще оставалось место, им пришлось бы переместить всего несколько книг, чтобы освободить место для новой. Это основной принцип библиотечной сортировки.
Алгоритм был предложен Майклом А. Бендером , Мартином Фарах-Колтоном и Мигелем Мостейро в 2004 году. [1] и был опубликован в 2006 году. [2]
Как и сортировка вставкой, на которой она основана, библиотечная сортировка является сортировкой сравнения ; однако было показано, что он имеет высокую вероятность выполнения за время O(n log n) (сравнимо с быстрой сортировкой ), а не за время сортировки вставками O(n 2 ). В статье не приводится ни полная реализация, ни точные алгоритмы важных частей, таких как вставка и ребалансировка. Потребуется дополнительная информация, чтобы обсудить, насколько эффективность библиотечной сортировки сравнивается с эффективностью других методов сортировки в реальности.
По сравнению с базовой сортировкой вставками, недостатком библиотечной сортировки является то, что она требует дополнительного места для пробелов. Объем и распределение этого пространства будут зависеть от реализации. В статье размер необходимого массива равен (1 + ε)n , [2] но без дальнейших рекомендаций по выбору ε. Более того, он не является ни адаптивным, ни стабильным. Чтобы гарантировать временные границы с высокой вероятностью, он должен случайным образом переставлять входные данные, что изменяет относительный порядок равных элементов и перемешивает любые предварительно отсортированные входные данные. Кроме того, алгоритм использует двоичный поиск для поиска точки вставки для каждого элемента, при этом не используются преимущества предварительно отсортированного ввода.
Еще одним недостатком является то, что его нельзя запустить как онлайн-алгоритм , поскольку невозможно случайно перетасовать входные данные. Если использовать его без этой перетасовки, оно может легко переродиться в квадратичное поведение.
Одним из недостатков сортировки вставкой является то, что она может потребовать большого количества операций подкачки и быть дорогостоящей, если запись в память обходится дорого. Библиотечная сортировка может несколько улучшить ситуацию на этапе вставки, поскольку меньше элементов нужно переместить, чтобы освободить место, но также добавляет дополнительные затраты на этапе перебалансировки. Кроме того, локальность ссылки будет плохой по сравнению с сортировкой слиянием , поскольку каждая вставка из случайного набора данных может получить доступ к памяти, которой больше нет в кеше, особенно с большими наборами данных.
Выполнение
[ редактировать ]Алгоритм
[ редактировать ]Допустим, у нас есть массив из n элементов. Мы выбираем разрыв, который намерены оставить. Тогда у нас будет конечный массив размером (1 + ε)n. Алгоритм работает за лог n раундов. В каждом раунде мы вставляем столько элементов, сколько уже есть в конечном массиве, прежде чем выполнить повторную балансировку массива. Чтобы найти позицию вставки, мы применяем двоичный поиск в конечном массиве, а затем меняем местами следующие элементы, пока не наткнемся на пустое место. По завершении раунда мы повторно балансируем окончательный массив, вставляя пробелы между каждым элементом.
Ниже приведены три важных шага алгоритма:
- Бинарный поиск : поиск позиции вставки путем применения бинарного поиска внутри уже вставленных элементов. Это можно сделать, линейно перемещаясь к левой или правой части массива, если вы нажмете на пустое место в среднем элементе.
- Вставка : вставка элемента в найденную позицию и замена следующих элементов на 1 позицию до тех пор, пока не появится пустое место. С высокой вероятностью это делается за логарифмическое время.
- Ребалансировка : вставка пробелов между каждой парой элементов массива. Стоимость ребалансировки линейно зависит от количества уже вставленных элементов. Поскольку эти длины увеличиваются со степенью двойки в каждом раунде, общая стоимость ребалансировки также является линейной.
Псевдокод
[ редактировать ]procedure rebalance(A, begin, end) is
r ← end
w ← end × 2
while r ≥ begin do
A[w] ← A[r]
A[w-1] ← gap
r ← r − 1
w ← w − 2
procedure sort(A) is
n ← length(A)
S ← new array of n gaps
for i ← 1 to floor(log2(n-1)) do
rebalance(S, 1, 2^(i-1)))
for j ← 2^(i-1) to 2^i do
ins ← binarysearch(A[j], S, 2^i)
insert A[j] at S[ins]
Здесь, binarysearch(el, A, k) выполняет двоичный поиск в первых k элементах A , пропуская пробелы, чтобы найти место, где можно найти элемент el . При вставке следует отдавать предпочтение пробелам, а не заполненным элементам.
Ссылки
[ редактировать ]- ^ Бендер, Майкл А.; Фарах-Колтон, Мартин ; Мостейру, Мигель А. (1 июля 2004 г.). «Сортировка вставками — O(n log n)». arXiv : cs/0407003 .
- ^ Jump up to: Перейти обратно: а б Бендер, Майкл А.; Фарах-Колтон, Мартин ; Мостейро, Мигель А. (июнь 2006 г.). «Сортировка вставками — O (n log n)» (PDF) . Теория вычислительных систем . 39 (3): 391–397. arXiv : cs/0407003 . дои : 10.1007/s00224-005-1237-z . S2CID 14701669 . Архивировано из оригинала (PDF) 8 сентября 2017 г. Проверено 7 сентября 2017 г.