Сортировка библиотеки - Library sort
 | Эта статья нужны дополнительные цитаты для проверка. (Октябрь 2017 г.) (Узнайте, как и когда удалить этот шаблон сообщения) |
| Учебный класс | Алгоритм сортировки |
|---|---|
| Структура данных | Множество |
| Худший случай спектакль | |
| Лучший случай спектакль | |
| Средний спектакль | |
| Худший случай космическая сложность |
Сортировка библиотеки, или же сортировка вставки с разрывом это алгоритм сортировки который использует вставка сортировки, но с пробелами в массиве для ускорения последующих вставок. Название происходит от аналогии:
Предположим, библиотекарь хранит свои книги в алфавитном порядке на длинной полке, начиная с буквы «А» на левом конце и продолжая вправо вдоль полки без промежутков между книгами до конца «буква Z». Если библиотекарь приобрел новую книгу, принадлежащую к секции B, как только он найдет правильное место в секции B, ему придется переместить каждую книгу, от середины B до Z, чтобы освободите место для новой книги. Это сортировка вставкой. Однако, если бы он оставил пробел после каждой буквы, пока еще оставался пробел после B, ему нужно было бы только переместить несколько книг, чтобы освободить место для новой. Это основной принцип сортировки библиотеки.
Алгоритм был предложен Майкл А. Бендер, Мартин Фарач-Колтон, и Мигель Мостейро в 2004 году[1] и был опубликован в 2006 году.[2]
Как и сортировка вставкой, на которой она основана, сортировка библиотеки - это сортировка сравнения; однако было показано, что он имеет высокую вероятность работы за время O (n log n) (сравнимо с быстрая сортировка ), а не сортировка вставкой O (n2). В документе не приводится ни полной реализации, ни точных алгоритмов важных частей, таких как вставка и ребалансировка. Дополнительная информация потребуется, чтобы обсудить, как эффективность библиотечной сортировки сравнивается с эффективностью других методов сортировки в реальности.
По сравнению с базовой сортировкой вставкой недостатком библиотечной сортировки является то, что для нее требуется дополнительное пространство для пробелов. Количество и распределение этого пространства будут зависеть от реализации. В статье размер необходимого массива (1 + ε) п,[2] но без дальнейших рекомендаций по выбору ε. Более того, он не адаптивен и не стабилен. Чтобы гарантировать временные границы с высокой вероятностью, требуется случайным образом переставлять входные данные, что изменяет относительный порядок равных элементов и перемешивает любой предварительно отсортированный вход. Кроме того, алгоритм использует двоичный поиск, чтобы найти точку вставки для каждого элемента, который не учитывает предварительно отсортированный ввод.
Еще один недостаток в том, что его нельзя запускать как онлайн алгоритм, поскольку случайное перемешивание ввода невозможно. Если использовать без этой перетасовки, она может легко выродиться в квадратичное поведение.
Одна слабость вставка сортировки в том, что это может потребовать большого количества операций подкачки и быть дорогостоящим, если запись в память дорогая. Сортировка библиотеки может несколько улучшить это на этапе вставки, так как меньшее количество элементов нужно переместить, чтобы освободить место, но также добавляет дополнительные затраты на этапе перебалансировки. Кроме того, местоположение ссылки будет плохим по сравнению с Сортировка слиянием поскольку каждая вставка из случайного набора данных может обращаться к памяти, которой больше нет в кеше, особенно с большими наборами данных.
Выполнение
Алгоритм
Допустим, у нас есть массив из n элементов. Выбираем промежуток, который намереваемся дать. Тогда у нас будет окончательный массив размером (1 + ε) n. Алгоритм работает за log n раундов. В каждом раунде мы вставляем столько элементов, сколько уже есть в окончательном массиве, перед повторной балансировкой массива. Для нахождения позиции вставки мы применяем двоичный поиск в конечном массиве, а затем меняем местами следующие элементы, пока не достигнем пустого места. По окончании раунда мы повторно балансируем последний массив, вставляя пробелы между каждым элементом.
Ниже приведены три важных шага алгоритма:
- Бинарный поиск: Поиск позиции вставки путем применения бинарного поиска в уже вставленных элементах. Это можно сделать, линейно перемещаясь к левой или правой стороне массива, если вы попали в пустое место в среднем элементе.
- Вставка: Вставка элемента в найденную позицию и замена следующих элементов на 1 позицию, пока не будет достигнуто пустое место. Это делается в логарифмическом времени с большой вероятностью.
- Повторная балансировка: Вставка пробелов между каждой парой элементов в массиве. Стоимость перебалансировки линейна в зависимости от количества уже вставленных элементов. Поскольку эти длины увеличиваются с увеличением степени 2 для каждого раунда, общая стоимость ребалансировки также является линейной.
Псевдокод
процедура ребалансировка (A, начало, конец) является r ← конец w ← конец ÷ 2 пока г ≥ начало делать A [w + 1] ← пробел A [w] ← A [r] r ← r - 1 w ← w - 2
процедура сортировка (A) является n ← length (A) S ← новый массив из n пробелов за i ← от 1 до этажа (log2 (n) + 1) делать за j ← 2 ^ i до 2 ^ (i + 1) делать ins ← binarysearch (A [j], S, 2 ^ (i - 1)) вставить A [j] в S [ins]
Здесь, двоичный поиск (el, A, k) выполняет бинарный поиск во-первых k элементы А, пропуская пробелы, чтобы найти место, где разместить элемент эль. При вставке следует отдавать предпочтение пробелам, а не заполненным элементам.
Рекомендации
- ^ Бендер, Майкл А .; Фарах-Колтон, Мартин; Мостейро, Мигель А. (1 июля 2004 г.). «Сортировка вставкой - O (n log n)». arXiv:cs / 0407003.
- ^ а б Бендер, Майкл А .; Фарах-Колтон, Мартин; Мостейро, Мигель А. (июнь 2006 г.). "Сортировка вставкой - O (n log n)" (PDF). Теория вычислительных систем. 39 (3): 391–397. arXiv:cs / 0407003. Дои:10.1007 / s00224-005-1237-z. Архивировано из оригинал (PDF) на 2017-09-08. Получено 2017-09-07.