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

Question

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

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

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

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

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

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

Answer 1

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

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

Answer 2

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

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

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

Мне интересно, использует ли последнее решение на месте алгоритм стабильной сортировки за сценой.

Answer 3

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

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

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

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

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