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