Эффективный алгоритм частичной сортировки по N несортированным группам
Я ищу эффективный алгоритм для выполнения следующего: учитывая массив из N элементов, сортируйте его таким образом, чтобы элементы представляли собой M равных групп, где каждая группа не отсортирована, но группы отсортированы между собой (все элементы в одной группе меньше, чем любой элемент следующей группы).
Самый простой способ - просто отсортировать весь массив. Но это неэффективно, особенно если количество групп намного меньше, чем общее количество предметов (например, разбить миллион предметов на 5 групп).
В настоящее время я остановился на использовании алгоритма быстрого выбора (в частности, это разновидность Floyd-Rivest), который сортирует массив по 2 несортированным группам, а затем применяет его M-1 раз. Существенным улучшением может быть применение подхода "разделяй и властвуй" для быстрого выбора, сначала сортировка массива по двум группам, затем сортировка каждой половины и т. Д., Пока у нас не будет M групп. Вид обобщения неупорядоченной задачи частичной сортировки.
Но у меня есть интуитивное ощущение, что может быть более простой и эффективный подход к проблеме. Я что-то пропустил? Есть идеи? Мне это нужно для улучшения производительности массовой вставки в мою библиотеку RBush JavaScript (эффективная реализация R*-дерева).
1 ответ
Вот переформулировка проблемы. Вам нужно одновременно найти элементы ранжирования M-1 и использовать их для разделения массива на M несортированных групп.
Я бы посоветовал начать со стандартного быстрого выбора со случайными опорными точками, выбранными так, чтобы они были близки к медиане (для оценки этого сделайте трюк со случайной подвыборкой), для каждого случая, разделив массив на 2, а также разделив список ранжированных элементов, которые необходимо найти в 2 также. Продолжайте до тех пор, пока не дойдете до уровня, где у вас есть элемент ранжирования для поиска в текущей группе. Затем переключитесь на вариант быстрого выбора Floyd-Rivest, чтобы фактически найти этот элемент, и разделите текущую группу на 2. Затем, вернувшись из быстрого выбора, вы можете легко собрать вместе M групп, которые вам нужны.
Этот подход имеет ожидаемое время выполнения O(N log(M))
с довольно хорошими константами. Я сомневаюсь, что значительно лучше, чем это выполнимо.