#include "sorts.h"

template<class T> void Swap(T& a,T& b)
{
  T temp;
  temp=a;
  a=b;
  b=temp;
}


// a generic bubble sort
// it is not the most efficient way to do it
template<class X> void Bubble( X* data,int size )
{
 register int a,b;
 X t;

 for(a=1; a < size ; a++)
   for(b=size-1; b >= a; b--)
     if(data[b-1] > data[b])
        Swap(data[b-1],data[b]);
}


// a generic exchangesort
// it is not the most efficient way to do it
template<class X> void ExchangeSort(X* data,int size)
{
 int i,j;
 //to make size-1 ways
 //take a minimum from a[i+1] ... a[size-1] and place into a[i]
 for(i=0; i<size-1; i++)
   for(j=i+1; j<size; j++)
	  if(data[i] > data[j])
		Swap(data[i],data[j]);
}


template <class T> void InsertionSort(T *data,int size)
{
 int i,j;
 T temp;
 for(i=1; i<size; i++)
 {

  j=i;
  temp=data[i];
  while(j>0 && temp < data[j-1])
  {
    //to move the elements right for the insertion of temp
    data[j] = data[j-1];
    j--;
  }

  data[j]=temp;
 }
}

template<class T> void SelectionSort(T* data,int size)
{
 int small,i,j;
 for(i=0; i< size-1; i++)
 {
   small=i;
   for(j=i+1; j<size; j++)
     if(data[j] < data [small])
       small=j;


   Swap(data[i],data[small]);
 }
}


template <class X> void BubbleSort( X *data,int size )
{
  // i index of the last element in the sublist
  int i,j,lastExchange;
  i=size-1;
  // make htis process till no swaps were done
  while(i>0)
  {
   lastExchange=0;  //initialization to permite the stop of process
   // working on sublist  data[0] -- data[i]
   for(j=0; j<i; j++)
     if(data[j+1] < data[j])
     {
      Swap(data[j],data[j+1]);
      lastExchange= j;
     }
   // i should take the value of last exchange index
   i=lastExchange;
  }
}