Ответ 1

Это не сортировка

По крайней мере, не как библиотека std определяет ее виды.

Вы просто хотите переместить некоторые элементы вокруг.

4 шага:

• Найдите первый A. Здесь мы хотим переместить Cs.

• Стабильный раздел всех C должен быть справа перед первым A.

• Найдите последний A. Это то, где мы хотим засунуть Bs.

• Стабильный раздел Bs должен быть справа после последнего A.

Все Cs до первого A остаются неподвижными. Все Bs после последнего A остаются неподвижными.

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

Все, что не является C или B, сохраняет свой относительный порядок.

код:

template<class It, class IsA, class IsB, class IsC>
void do_it(It s, It f, IsA a, IsB b, IsC c){
  auto first_a = std::find_if(s,f,a);
  first_a = std::stable_partition(first_a,f,c);
  auto last_a = std::find_if(std::make_reverse_iterator(f), std::make_reverse_iterator(first_a), a).base();
  std::stable_partition(s,last_a, [&b](auto&&x){return !b(x);});
}

Живой пример.

С достаточной запасной памятью, это выше O (n).

Конечно, это можно просто сделать в одной строке:

std::stable_partition(s,std::find_if(std::make_reverse_iterator(f), std::make_reverse_iterator(std::stable_partition(std::find_if(s,f,a),f,c)), a).base(), [&b](auto&&x){return !b(x);});

но я бы не рекомендовал его.

Ответ 2

Это не строгий слабый порядок, но это частичное упорядочение. Алгоритм сортировки с помощью частичного упорядочения называется топологической сортировкой, как это наивная реализация:

template <typename Iterator, typename Compare>
void stable_toposort(Iterator begin, Iterator end, Compare cmp)
{
    while (begin != end)
    {
        auto const new_begin = std::stable_partition(begin, end, [&](auto const& a)
        {
            return std::none_of(begin, end, [&](auto const& b) { return cmp(b, a); });
        });
        assert(new_begin != begin && "not a partial ordering");
        begin = new_begin;
    }
}

Он разбивает последовательность так, что все элементы, которые не больше любого другого элемента, перемещаются в начало. Затем он принимает все остальные элементы и разбивает их таким же образом, пока не останется больше элементов, которые будут разбиты на разделы. Его сложность - это O (n & sup2;) сравнения и O (n) свопы.

Затем нам нужно исправить ошибку в функции сравнения:

bool CompareItems(SItem const& item1, SItem const& item2)
{
    if (item1.type == C && item2.type == A) return true;
    if (item1.type == A && item2.type == B) return true;
    return false;
}

Live demo

Для справки, нестабильная версия будет использовать partition вместо stable_partition.

Ответ 3

То, что вы хотите, - это своего рода стабильная топологическая сортировка. Ваша группа DAG - это точка Cs в точке As в точке B. См. fooobar.com/questions/288453/... описание достаточно эффективного алгоритма для реализации топологической сортировки, которая является самой низкой в ​​лексикографическом (в вашем исходном списке) порядке. Его вывод в вашем случае будет:

C1, F, G, C2, A1, A2, A3, H, A4, B

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

Ответ 4

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

void slide_bs_and_cs( std::list<SItem>& all ) {
    // Don't touch if no A found:
    if ( std::find(all.begin(), all.end(),
        [](const SItem& item) { return item->type == A; }) == all.end() )
        return;

    std::list<SItem> bs;
    std::list<SItem> cs;
    auto first_a = all.end();
    auto after_last_a = all.end();
    for ( auto it = all.begin(); it != all.end();
          /*advanced in loop*/ ) {
        auto next = it;
        ++next;
        if ( (*it)->type == A ) {
            after_last_a = next;
            if ( first_a == all.end() )
                first_a = it;
        } else if ( (*it)->type == B ) {
            bs.splice( bs.end(), it );
        } else if ( (*it)->type == C ) {
            cs.splice( cs.end(), it );
        }
        it = next;
    }
    all.splice( first_a, cs );
    all.splice( after_last_a, bs );
}

Ответ 5

Проблема с нестрогим слабым упорядочением состоит в том, что для определения отсортированного списка недостаточно порядка. При вводе A1, B, C1, A2, A3, F, G, C2, H, A4 вы предложили выход C1 C2 A1 A2 A3 F G H A4 B. Но на самом деле B пришел до H в исходном списке и теперь идет, после чего не соответствует стабильному виду. Если вы хотите сохранить B < H, вы можете получить следующий список:

C1 C2 A1 A2 A3 F G A4 B H

но здесь это A4, H, который был сломан.

Чтобы построить стабильный вид, вы должны определить строгий слабый порядок. Чтобы получить список, который вы предлагаете, этот порядок можно использовать:

• C предшествует A
• B появляется после A
• все остальные буквы эквивалентны A

В этом случае функция сравнения становится:

bool CompareItems(SItem const& item1, SItem const& item2) 
{
    if (item1.type == 'C' && item2.type != 'C')
        return true;

    if (item1.type != 'B' && item2.type == 'B')
        return true;

    return false;
}

В качестве альтернативы вы можете попытаться указать алгоритм, который принимает не слабый строгий порядок, но вам нужно будет указать, что произойдет, если у вас есть этот оригинальный список X Y Z, Z < X, X,Y и Y,Z не сопоставимы: вы хотите Z X Y, Z Y X или Y Z X? На самом деле это зависит от того, должен ли Y обрабатываться как эквивалент X или Z или... И тогда задайтесь вопросом, что может произойти в более сложных случаях использования...