Home

Sorting on a non-StrictWeak Ordering

/* My results for this program:

$ c++ sort.cpp -o /tmp/sort && /tmp/sort
before sorting: 0x7 0x4 0x8 0x8 0xa 0x2 
after sorting: 0x4 0x7 0x8 0x8 0x2 0xa 
Oops! 0x2 followed 0x7

*/

#include <algorithm>
#include <vector>
#include <cstdlib>
#include <cassert>
#include <iostream>

#define _GLIBCXX_DEBUG 1

// Are a's bits a strict subset of b's?
// This is a strict partial, but not a strict weak, ordering!
inline bool compare(unsigned a, unsigned b)
{
    return a != b 
        && (a & b) == a;
}

typedef std::vector<unsigned> vec;

void print(vec const& v)
{
    std::cout << std::hex;
    for (std::size_t i = 0; i < v.size(); ++i)
        std::cout << "0x" << v[i] << " ";
    std::cout << std::endl;
}

int main()
{
    vec v;
    
    // For me this failed with only 4 numbers and a maximum of 15.
    // Your standard library implementation may require increasing one
    // or both of these numbers
    unsigned const maximum = 15;
    v.reserve(6);

    // Insert a few random numbers
    while (v.size() < v.capacity())
        v.push_back((unsigned)std::rand() % maximum);
    std::cout << "before sorting: ";
    print(v);


    std::sort(v.begin(), v.end(), compare);

    std::cout << "after sorting: ";
    print(v);

    int result = EXIT_SUCCESS;

    // Do an n^2 comparison of every element with every element that
    // comes later than it in the sequence
    for (std::size_t i = 0; i < v.size(); ++i)
    {
        for (std::size_t j = i + 1; j < v.size(); ++j)
        {
            // This comparison should never return true if the sort worked
            if (compare(v[j], v[i]))
            {
                std::cout << std::hex << "Oops! 0x" << v[j] << " followed 0x" << v[i] << std::endl;
                result = EXIT_FAILURE;
            }
        }
    }
    return result;
}