Flashsort - Flashsort - Wikipedia

Flashsort это сортировка распределения алгоритм, показывающий линейная вычислительная сложность ${\displaystyle O(n)}$ для равномерно распределенных наборов данных и относительно небольших требований к дополнительной памяти. Оригинальная работа была опубликована в 1998 году Карлом-Дитрихом Нойбертом.^[1]

Концепция

Основная идея flashsort заключается в том, что в наборе данных с известным распределение, легко сразу оценить, где должен быть размещен элемент после сортировки, когда известен диапазон набора. Например, если дан унифицированный набор данных, где минимум 1, а максимум 100, а 50 является элементом набора, разумно предположить, что 50 будет примерно в середине набора после его сортировки. Это примерное местоположение называется классом. Если пронумеровано от 1 до ${\displaystyle m}$, класс предмета ${\displaystyle A_{i}}$ это квантиль, вычисляется как:

  ${\displaystyle K(A_{i})=1+{\textrm {INT}}\left((m-1){\frac {A_{i}-A_{\textrm {min}}}{A_{\textrm {max}}-A_{\textrm {min}}}}\right)}$

куда ${\displaystyle A}$ - входной набор. Диапазон, охватываемый всеми классами, одинаков, за исключением последнего класса, который включает только максимум (и). Классификация гарантирует, что каждый элемент в классе больше любого элемента в более низком классе. Это частично упорядочивает данные и сокращает количество инверсий. Вставка сортировки затем применяется к классифицированному набору. Пока данные распределены равномерно, размеры классов будут согласованными, а сортировка вставкой будет эффективна в вычислительном отношении.^[1]

Реализация с эффективным использованием памяти

Чтобы выполнить flashsort с его преимуществами низкой памяти, алгоритм не использует дополнительные структуры данных для хранения классов. Вместо этого он хранит верхние границы каждого класса во входном массиве ${\displaystyle A}$ во вспомогательном векторе ${\displaystyle L}$. Эти верхние границы получаются путем подсчета количества элементов в каждом классе, а верхняя граница класса - это количество элементов в этом классе и каждом предшествующем ему классе. Эти границы служат указателями на классы.

Классификация реализуется через серию циклов, где лидер цикла берется из входного массива. ${\displaystyle A}$ и его класс рассчитан. Указатели в векторе ${\displaystyle L}$ используются для вставки лидера цикла в правильный класс, а указатель класса в ${\displaystyle L}$ уменьшается после каждой вставки. Вставка лидера цикла вытеснит другой элемент из массива ${\displaystyle A}$, который будет классифицирован и вставлен в другое место и так далее. Цикл завершается, когда элемент вставляется в начальную позицию лидера цикла.

Элемент является действительным лидером цикла, если он еще не был классифицирован. Поскольку алгоритм выполняет итерацию по массиву ${\displaystyle A}$, ранее классифицированные элементы пропускаются, а неклассифицированные элементы используются для запуска новых циклов. Можно определить, был ли элемент классифицирован или нет, без использования дополнительных тегов: если элемент был классифицирован, его индекс больше, чем верхняя граница его класса в ${\displaystyle L}$. Исходя из этого, мы можем найти все несекретные элементы в ${\displaystyle O(n)}$ общее время, сохраняя единственный указатель ${\displaystyle j}$ который изначально указывает на начало ${\displaystyle A}$ и постепенно перемещается вправо, пока не будет найден неклассифицированный элемент. Этот неклассифицированный элемент идентифицируется по индексу, меньшему или равному верхней границе его класса. Затем этот элемент становится лидером кольца, выполняется перестановка кольца и ${\displaystyle j}$ увеличивается. Этот процесс повторяется до тех пор, пока ${\displaystyle j}$ достигает конца ${\displaystyle A}$, после чего классифицируются все элементы.^[1][2]

Спектакль

Единственные дополнительные требования к памяти - это вспомогательный вектор. ${\displaystyle L}$ для хранения границ классов и постоянного числа других используемых переменных.

В идеальном случае сбалансированного набора данных каждый класс будет примерно одинакового размера. Если число ${\displaystyle m}$ классов линейно по размеру ввода ${\displaystyle n}$, каждый класс имеет постоянный размер, поэтому сортировка одного класса сложна ${\displaystyle O(1)}$. Время выполнения последней сортировки вставкой ${\displaystyle m\cdot O(1)=O(m)=O(n)}$. В наихудших сценариях, когда почти все элементы находятся в нескольких или одном классе, сложность алгоритма ограничивается производительностью метода сортировки на последнем шаге. Для сортировки вставкой это ${\displaystyle O(n^{2})}$. Варианты алгоритма улучшают производительность в худшем случае за счет использования более эффективных сортировок, таких как быстрая сортировка или рекурсивная флеш-сортировка для классов, размер которых превышает определенный лимит.^[2][3]

Выбор значения для ${\displaystyle m}$, количество классов, время, потраченное на классификацию элементов (высокий ${\displaystyle m}$) и время, затраченное на последнем этапе сортировки вставкой (низкий ${\displaystyle m}$).

С точки зрения памяти, flashsort позволяет избежать накладных расходов, необходимых для хранения классов в очень похожих ведро сортировка. За ${\displaystyle m=0.1n}$ с равномерно распределенными случайными данными flashsort выполняется быстрее, чем heapsort для всех ${\displaystyle n}$ и быстрее, чем quickersort для ${\displaystyle n>80}$. Скорость сортировки увеличивается примерно в два раза. ${\displaystyle n=10000}$.^[1]

Из-за на месте перестановка, которую выполняет flashsort в процессе классификации, flashsort не стабильный. Если требуется стабильность, можно использовать второй массив, чтобы элементы можно было классифицировать последовательно. Однако в этом случае алгоритм потребует ${\displaystyle O(n)}$ Космос.

Смотрите также

• Поиск с интерполяцией, используя распределение предметов для поиск вместо сортировки

Рекомендации

1. Neubert, Карл-Дитрих (февраль 1998 г.). "Алгоритм Flashsort". Журнал доктора Добба: 123. Получено 2007-11-06.
2. Карл-Дитрих Нойберт (1998). «Алгоритм FlashSort». Получено 2007-11-06.
3. Ли Сяо; Сяодун Чжан; Стефан А. Кубрихт. «Быстрая сортировка с эффективностью кеширования». Повышение производительности памяти алгоритмов сортировки. Департамент компьютерных наук, Колледж Уильяма и Мэри, Вильямсбург, VA 23187-8795. Архивировано из оригинал на 2007-11-02. Получено 2007-11-06.

внешняя ссылка

• Реализации рандомизированной сортировки на больших параллельных машинах (1992)
• Реализация параллельных алгоритмов (1992)
• Визуализация Flashsort