Стабильное разделение для двух классов элементов в массиве

Рассмотрим следующую проблему.

Нам дан массив элементов, принадлежащих одному из двух классов: красный или синий. Мы должны переставить элементы массива так, чтобы все синие элементы были первыми (а все красные элементы следовали). Перестановка должна быть сделана устойчивым способом, означая, что относительный порядок синих элементов должен быть сохранен (то же самое для красных).

Есть ли умный алгоритм, который бы выполнял вышеуказанную перестановку на месте?

Решение не на месте, конечно, просто.

Очевидным решением на месте было бы применить любой устойчивый алгоритм сортировки к массиву. Однако использование полноценного алгоритма сортировки в массиве интуитивно кажется избыточным, особенно с учетом того факта, что мы имеем дело только с двумя классами элементов.

Любые идеи с благодарностью.

Источник

3 ответа

Решение

По-видимому, это можно сделать за время O(n) и пространство O(1). Юрки Катаяйнен (Jyrki Katajainen) и Томи Пасанен утверждают, что могут сделать это.

Google для стабильной сортировки 0-1.

Источник

Это называется стабильным разделением в C++, и для этого есть стандартный алгоритм: std:: stable_partition.

Реализация SGI имеет адаптивное поведение в зависимости от объема доступной памяти:

  • он работает в O(N), если возможно выделить O(N) пространство
  • он работает в O(N log N) на месте

Я действительно задаюсь вопросом, использует ли последнее решение на месте устойчивый алгоритм сортировки за кулисами.

Источник

Я не знаю алгоритм O(n), но вот простой алгоритм со сложностью O(n*log(n)) в худшем случае. Может быть, это будет полезно.

Отрежьте нули от начала и до конца, они уже на своих местах. Теперь массив выглядит как последовательность единиц, за которой следует последовательность нулей, за которой следует последовательность единиц и т. Д., Например: 1010101010

Замените первую последовательность единиц на первую последовательность нулей, третью последовательность единиц на третью последовательность нулей и так далее. Станет: 0110011001

Количество последовательностей стало примерно вдвое меньше. Повторяйте вышеописанную процедуру, пока массив не будет отсортирован.

Для обмена двумя соседними последовательностями поменяйте местами первую, затем вторую, а затем поменяйте их обе.

Источник
Другие вопросы по тегам