shaker sort

shaker.cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <ctime>

template<typename BidirectionalIterator>
void bubble_sort( BidirectionalIterator first, BidirectionalIterator last )
{
	if( first == last ) return;

	for( BidirectionalIterator i = --last; i != first; --i ){
		for( BidirectionalIterator j=first; j != i; ++j ){
			BidirectionalIterator k = j;
			++k;
			if( *j > *k )
				swap_value(j, k);
		}
	}
}

template<typename BidirectionalIterator>
void shaker_sort( BidirectionalIterator first, BidirectionalIterator last )
{
	if( first == last ) return;
	
	BidirectionalIterator seek_tail = --last;
	BidirectionalIterator seek_head = first;
	while( seek_tail != seek_head ){
		BidirectionalIterator i = seek_head;
		for( BidirectionalIterator j=seek_head; j != seek_tail; ++j ){
			BidirectionalIterator k = j;
			++k;
			if( *j > *k ){
				swap_value(j, k);
				i = j;
			}
		}
		seek_tail = i;

		i = seek_tail;
		for( BidirectionalIterator j=seek_tail; j != seek_head; --j ){
			BidirectionalIterator k = j;
			--k;
			if( *j < *k ){
				swap_value(j, k);
				i = j;
			}
		}
		seek_head = i;
	}
}

template<typename Iterator>
void swap_value( Iterator i, Iterator j )
{
	typename Iterator::value_type tmp = *i;
	*i = *j;
	*j = tmp;
}

typedef std::vector<int> Container;

template<typename ForwardIterator>
bool check_if_sorted( ForwardIterator first, ForwardIterator last)
{
	ForwardIterator i = first;
	ForwardIterator j = first;
	++j;
	while( j != last ){
		if( *i > *j ) return false;
		++i;
		++j;
	}
	return true;
}

class getRandom
{
	int m_randmax;
public:
	getRandom( int randmax=RAND_MAX	) : m_randmax(randmax) {}
	int operator() () { return rand()%m_randmax; }
};

class getSequence
{
	int m_num;
public:
	getSequence( int start=0 ) : m_num(start) {}
	int operator() () { return m_num++; }
};

int main()
{
	const size_t NUM_DATA = 10000;
	srand(1);

	Container testdata;
	std::generate_n(std::back_inserter(testdata), NUM_DATA, getRandom());

	clock_t t0, t1;
	std::cout << "Bubble sort" << std::endl;

   	t0 = clock();
	bubble_sort(testdata.begin(), testdata.end());
	t1 = clock();
	std::cout << static_cast<double>(t1-t0)/CLOCKS_PER_SEC << " seconds" << std::endl;

	if( check_if_sorted(testdata.begin(), testdata.end()) )
		std::cout << "sorting is complete" << std::endl;

	testdata.clear();
	std::generate_n(std::back_inserter(testdata), NUM_DATA, getRandom());

	std::cout << "Shaker sort" << std::endl;

   	t0 = clock();
	shaker_sort(testdata.begin(), testdata.end());
	t1 = clock();
	std::cout << static_cast<double>(t1-t0)/CLOCKS_PER_SEC << " seconds" << std::endl;

	if( check_if_sorted(testdata.begin(), testdata.end()) )
		std::cout << "sorting is complete" << std::endl;

}