Стабильное разделение для двух классов элементов в массиве
Рассмотрите следующую проблему.
Нам дают массив элементов, принадлежащих двум классам: или красный или синий. Мы должны перестроить элементы массива так, чтобы все синие элементы были на первом месте (и все красные элементы следуют). Перестановка должна быть сделана, стабильный вид, означая, что относительный порядок синих элементов должен быть сохранен (то же для красных).
Существует ли умный алгоритм, который выполнил бы вышеупомянутую оперативную перестановку?
Нена месте решение, конечно, просто.
Очевидное оперативное решение состояло бы в том, чтобы применить любой стабильный алгоритм сортировки к массиву. Однако использование законченного алгоритма сортировки на массиве интуитивно чувствует себя подобно излишеству, особенно принимая во внимание то, что мы только имеем дело с двумя классами элементов.
Любые идеи значительно ценятся.
3 ответа
Очевидно, это можно сделать за O (n) время и O (1) пространство. В статье Стабильное минимальное разбиение пространства за линейное время Юрки Катаяйнен и Томи Пасанен утверждают, что они могут это сделать.
Google для стабильной сортировки 0-1.
Я не знаю алгоритма O (n), но вот простой алгоритм со сложностью O (n * log (n)) в худшем случае. Может быть, будет полезно.
Отрежьте нули с начала и единицы с конца, они уже на своих местах. Теперь массив выглядит как последовательность единиц, за которой следует последовательность нулей, за которой следует последовательность единиц и так далее, например: 1010101010
Замените первую последовательность единиц первой последовательностью нулей, третью последовательность единиц - на третья последовательность нулей и так далее. Он станет: 0110011001
Количество последовательностей стало примерно вдвое меньше. Повторяйте описанную выше процедуру до тех пор, пока массив не будет отсортирован.
Чтобы поменять местами две соседние последовательности, поменяйте местами сначала первую, затем вторую, а затем обе.
Это называется стабильным разделением в C ++, и для этого существует стандартный алгоритм: std :: stable_partition .
Реализация SGI имеет адаптивное поведение в зависимости от объема доступной памяти:
- она выполняется за O (N), если возможно выделить O (N) пространства
- , она выполняется за O (N log N) swaps in place
Мне интересно, использует ли последнее решение на месте стабильный алгоритм сортировки за кулисами.