// This program implements the Bubble sort algorithm (page 76 of Skansholm)
// using a vector to contain the data and vector iterators to access the elements
#include <iostream>
#include <ctime>
#include <cstdlib>
#include <ctime>

#include <vector>

void swap( vector<int>::iterator p, vector<int>::iterator q)
{	int pv = *p;
	*p=*q;
	*q=pv;
}
void sort( vector<int>::/******/ begin, vector<int>::iterator end)
{
  int swaps;
  do{
	swaps=0;
	for(vector<int>::iterator p = begin+1; p != end; p++)
	{
		if(*(p-1)>*p)
		{
			swaps++;
			swap(p-1, p);
		}
	}
  }while(swaps > 0);

}

int main()
{
   const int seed = static_cast<int>(time(0));
   srand(seed);//set random number differently each run

   const int Biggest = 100000;
   const int Size = 5000;
   const int Sample = 100;

   double total_time =0.0;

   for(int s = 0; s<Sample; s++)
   { 
      vector <int> data;
      for(int i = 0; i< Size; i++)
      {
	   data.push_back(rand()%Biggest);
      }

      time_t time1 = time(0);
      sort(data.begin(), data.end());
      time_t time2 = time(0);

      total_time+= difftime(time2, time1);
   }

   cout << "Bubble Sort. Size =" << Size << ", mean time =";
   cout << total_time /Sample;

   return 0;
}