//This program implements the well known Selection Sort Algorithm 
// This is a handcoded version, 
// unlike timeSelectionSort.cpp that uses <algorithm>
#include <iostream>
#include <ctime>
#include <cstdlib>
#include <ctime>

#include <vector>


using namespace std;

void swap(vector<int> &v, int p, int q)
{       int vp = v[p];
        v[p]=v[q];
        v[q]=vp;
}
void sort( vector<int>&v, int begin, int end)
{
        int next;
    
        for (next = begin; next != end-1; next++)
	{
            int min_pos = next;
	    int i;
            for (i = next + 1; i != end; i++)
                if (v[i] < v[min_pos])
                    /********/ = i;

	    if ( min_pos != next)
		    swap(v, next, min_pos);
        }//for next

}

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, 0, data.size());
      time_t time2 = time(0);

      total_time+= difftime(time2, time1);
   }

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

   return 0;
}