Simple Vector Sort

simplesort.cpp

#include <assert.h>
#include <stdlib.h>
#include <vector>

struct test_t {

    bool operator < (const test_t & rhs) const {
        return value_<rhs.value_;
    }

    bool operator <= (const test_t & rhs) const {
        return value_<=rhs.value_;
    }

    int value_;
};

/* 
 * Very simple stable assending sort function:
 * - performs reasonably for small, nearly in-order lists; tends to o(N)
 * - performs badly for large, out-of-order lists; tends to o(N^2)
 */
template <typename type_t>
void simple_sort(std::vector<type_t> & vec) {
    const size_t size = vec.size();
    const type_t * first = &vec[0];
    for (size_t i = 1; i<size; ++i) {
        type_t * a = &vec[i-1];
        type_t * b = &vec[i-0];
        while ((b!=first)&&(*b<*a)) {
            std::swap(*a, *b);
            --a, --b;
        }
    }
}

int main(const int argc, const char ** args) {

    const size_t C_SIZE = 10000;
    std::vector<test_t> vec;

    vec.reserve(C_SIZE);
    for (size_t i = 0; i<C_SIZE; ++i)
        vec.push_back(test_t{int(rand() % C_SIZE)});

    simple_sort(vec);

    for (size_t i = 1; i<vec.size(); ++i)
        assert(vec[i-1]<=vec[i-0]);

    return 0;
}