Sorting a list with a comparison function that doesn't follow 'strict weak ordering'

Question

I have a list of 10 items. I would like sort them in a particular manner.

For eg. the items are A1, B, C1, A2, A3, F, G, C2, H, A4

Rules are

• C should always come before A
• B should always come after A
• All the other item should preserve their order.

So after sorting the list should be in this order C1 C2 A1 A2 A3 F G H A4 B

I am trying to use C++ std::stable_sort() method to achieve this. In my program all the items are instance of a structure 'SItem' which got a member 'type' to idicate its category(A, B etc). My comparison function looks like this

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

    if (item1.type == B && item2.type == A)
        return false;

    return true;
}

From my understanding of stable_sort, it requires the comparison function to follow 'strict weak ordering'. Obviously my method doesn't follow that, so I cannot use the stable_sort. Is their sorting algorithm available to achieve this type of orders?

Complete code

#include <list>
#include <algorithm>
#include <iostream>

enum ItemType
{
    A, B, C, D, E, F, G, H,
};

struct SItem
{
    SItem(ItemType t, int i) {
        type = t;
        index = i;
    }

    ItemType type;
    int index;
};

//do not follow strict week ordering
bool CompareItems(SItem const& item1, SItem const& item2) 
{
    if (item1.type == A && item2.type == C)
        return false;

    if (item1.type == B && item2.type == A)
        return false;

    return true;
}


int main()
{
    std::list<SItem> lstItems = { {A, 1}, {B, 1}, {C, 1}, {A, 2}, {A, 3}, {F, 1}, {G, 1}, {C, 2}, {H, 1}, {A, 4} };
    std::stable_sort(lstItems.begin(), lstItems.end(), CompareItems);

    return 0;
}

Answer 1

It is not a strict weak ordering, but it is a partial ordering. An algorithm for sorting by a partial ordering is called a topological sort, like this naive implementation:

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;
    }
}

It partitions the sequence so that all the elements that are not greater than any other element are moved to the front. Then it takes all the remaining elements and partitions them in the same way, until there remain no more elements to be partitioned. Its complexity is O(n²) comparisons and O(n) swaps.

Then we need to fix the bug in the comparison function:

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

For reference, an unstable version would use partition instead of stable_partition.

Answer 2

What you want is some sort of stable topological sort. Your DAG is that Cs point at As point at Bs. See https://stackoverflow.com/a/11236027/585411 for a description of a reasonably efficient algorithm to implement the topological sort that is lowest in lexicographic (in your original list) order. Its output in your case would be:

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

Thinking about it that way makes it easy to generalize lots of different kinds of rules that you might have, rather than special casing how this example works. So long as they don't add up to a circular path, your algorithm will still work.

Answer 3

This is not a sort

At least not as std library defines its sorts.

You just want to move some elements around.

4 steps:

• Find the first A. This is where we want to shove the Cs.

• Stable partition all C to be right before the first A.

• Find the last A. This is where we want to shove the Bs.

• Stable partition the Bs to be right after the last A.

All Cs before the first A remain stationary. All Bs after the last A remain stationary.

Cs keep their relative order. Bs keep their relative order. Both move the least possible to generate the guarantee you require.

Everything that isn't a C or a B keeps their relative order.

Code:

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);});
}

Live example.

With enough spare memory, the above is O(n).

Of course, this could simply be done in one line:

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);});

but I wouldn't recommend it.

Answer 4

The problem with a non strict weak ordering is that the order is not enough to define the sorted list. With the input A1, B, C1, A2, A3, F, G, C2, H, A4 you proposed the output C1 C2 A1 A2 A3 F G H A4 B. But in fact, B came before H in original list and now comes after which is not conformant with a stable sort. If you wanted to preserve B < H, you could get the following list:

C1 C2 A1 A2 A3 F G A4 B H

but here it is the A4 < H that has been broken.

To build a stable sort, you have to define a strict weak ordering. To obtain the list you propose, this order could be used:

• C comes before A
• B comes after A
• all other letters are equivalent to A

In that case, the compare function becomes :

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;
}

Alternatively, you could try to specify an algorithm that accepts a non weak strict ordering, but you will have to specify what happen when you have this original list X Y Z, Z < X, X,Y and Y,Z non comparable: do you want Z X Y, Z Y X or Y Z X? In fact it depends whether Y should be processed as equivalent to X or Z or... And then wonder what could happen in more complex use cases...

Answer 5

If I understand your desired algorithm right, it's probably easiest to just split manually into three lists and then splice back together.

void slide_bs_and_cs( std::list<SItem>& all ) {
    // Don't touch if no A's 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 );
}