ATL / WTL / STL

template <typename T>
void bubble(std::vector<T> &a)
{
   typedef typename std::vector<T>::iterator Iter;
   Iter last = a.end()-1;
   for(Iter pass=a.begin();pass!=last;++pass)
      for(Iter n=a.begin();n!=last;++n)
         if (*n > *(n+1))
            std::iter_swap(n, n+1);
}

template <typename T>
void bubble(std::vector<T> &a)
{
   typedef typename std::vector<T>::iterator Iter;
   for(Iter last = a.end()-1;last!=a.begin();--last)
      for(Iter n=a.begin();n!=last;++n)
         if (*n > *(n+1))
            std::iter_swap(n, n+1);
}

template <typename iterator> void bubble(iterator first, iterator last) { // O(n^2)
     iterator i, j;
     for (i = first; i != last; ++i)
         for (j = first; j < i; ++j)
             if (*i < *j)
                 std::iter_swap(i, j); // or std::swap(*i, *j);
}

template <class iterator> void gnome(iterator first, iterator last){ // O(n^2)
	iterator pos = first;
	iterator temp;
	while (pos <= last) {
		if ((pos == first) || (*pos >= *(pos-1)))
			++pos;
		else {
			//{int tmp = ar[i]; ar[i] = ar[i-1]; ar[--i] = tmp;}
			std::iter_swap(pos, pos-1);
			--pos;
		}
	}
}

#include <vector>
#include <iostream>
#include <iterator>

template <class iterator> void gnome(iterator first, iterator last){ // O(n^2)
  iterator pos = first;
  iterator temp;
  while (pos <= last) {
    if ((pos == first) || (*pos >= *(pos-1)))
      ++pos;
    else {
      //{int tmp = ar[i]; ar[i] = ar[i-1]; ar[--i] = tmp;}
      std::iter_swap(pos, pos-1);
      --pos;
    }
  }
}

int main(int, char**)
{
  std::vector<int> vec;
  
  vec.push_back(4);
  vec.push_back(3);
  vec.push_back(5);
  vec.push_back(-10);
  vec.push_back(13);
  vec.push_back(2);
  vec.push_back(1);
  
  gnome(vec.begin(), vec.end()-1);
  
  std::copy(vec.begin(), vec.end(), std::ostream_iterator<int>(std::cout, " "));
}

void RunGnomeSort(void) {
	size_t size = 10000;
	std::vector<int> data;
	data.resize(size);
	for (int i = 0; i < size; i++)
		data[i] = (int)rand();
	sort::gnome(data.begin(),data.end());
	//for (int i = 0; i < size; i++)
		//std::cerr << data[i] << std::endl;
	data.resize(0);
}