Sort.h
#pragma once

template <class TYPE>
class CSort
{
public:
	CSort(void);
	~CSort(void);
	void selectionSort(TYPE [], int);
	void insertionSort(TYPE [], int);
	void bubbleSort(TYPE [], int);
	void shellSort(TYPE [], int); 
	void quickSort(TYPE [], int);
	void heapSort(TYPE [], int);
	int getComparisions() const { return m_comparisions; }
	int getMovements() const { return m_movements; }

	void display() const;

private:

	int m_comparisions;
	int m_movements;

	string m_methodName;
	int m_dataSize;
	
	int m_quickSortMinSize;
	void rquickSort(TYPE [], int, int, int&, int&);
	void medianLeft(TYPE [], int, int, int&, int&);
	void quickInsertionSort(TYPE [], int, int, int&, int&);
	void shiftDown(TYPE [], int, int, int&, int&);


};




Sort.cpp

#include "StdAfx.h"
#include "Sort.h"

// för instansiering av templaten
template CSort<int>;
template CSort<double>;
template CSort<string>;
template CSort<float>;

template <class TYPE>
CSort<TYPE>::CSort(void)
{
	m_comparisions=m_movements=0;
	m_quickSortMinSize=10;
}


template <class TYPE>
CSort<TYPE>::~CSort(void)
{

}


///////////////////////////////////
// SELECTION SORT
// T(n) = A*n^2 + B*n
///////////////////////////////////

template <class TYPE>
void CSort<TYPE>::selectionSort(TYPE v[], int size)
{
	m_comparisions=m_movements=0;
	m_methodName="Selection sort";
	m_dataSize=size;

    for (int i=0; i<size-1; i++) {
	   int min_id = i;
       for (int j=i+1; j<size; j++)
           if (++m_comparisions, v[j] < v[min_id]) {
              min_id = j;
           }
	   swap(v[i], v[min_id]);
	   m_movements+=3;
   }

/*
	int i,j,minat;
	TYPE min;
	TYPE temp;
	for(i=0;i<(size-1);i++)
	{
		minat=i;
		min=v[i];

      for(j=i+1;j<(size);j++) //select the min of the rest of v
	  {
		  if(m_comparisions++,min>v[j])   //ascending order for descending reverse
		  {
			  minat=j;  //the position of the min element 
			  min=v[j];
			  m_movements++;
		  }
	  }
	  temp=v[i] ;
	  v[i]=v[minat];  //swap 
	  v[minat]=temp;
	  m_movements+=3;

		
	}*/


}


///////////////////////////////////
// INSERTION SORT
// T(n) = A*n^2 + B*n
///////////////////////////////////

template <class TYPE>
void CSort<TYPE>::insertionSort(TYPE v[], int size)
{
	m_comparisions=m_movements=0;
	m_methodName="Insertion sort";
	m_dataSize=size;


    for (int j=1; j<size; j++) {
       int i = j-1;
       TYPE tmp = v[j];
	   m_movements++;

       while ( (i>=0) && (++m_comparisions, tmp < v[i]) ) {
           v[i+1] = v[i];
		   m_movements++;
           i--;
       }
       v[i+1] = tmp;
	   m_movements++;
   }
}


///////////////////////////////////
// BUBBLE SORT
// T(n) = n^2
///////////////////////////////////


template <class TYPE>
void CSort<TYPE>::bubbleSort(TYPE v[],int size) 
{
	m_comparisions=m_movements=0;
	m_methodName="Bubble sort";
	m_dataSize=size;

   for (int i=0; i<size-1; i++) {
	   bool swapped=false;
	   for (int j=0; j<size-i-1; j++) {
            if (++m_comparisions, v[j] > v[j+1]) {
               swap(v[j], v[j+1]);
			   swapped=true;
			   m_movements+=3;
			}
	   }
	   if (!swapped)
		   break;
   }
}



///////////////////////////////////
// SHELL SORT
// T(n) = A*n^1.25
///////////////////////////////////


template <class TYPE>
void CSort<TYPE>::shellSort(TYPE v[], int size)
{
	m_comparisions=m_movements=0;
	m_methodName="Shell sort";
	m_dataSize=size;

	int incre=size/2;

	while (incre != 0)
	{
		for (int current=incre; current<size; current++)
		{
			TYPE temp=v[current];
			m_movements++;
			int i=current-incre; 
			while (++m_comparisions, i>=0 && temp<v[i])
			{
				v[i+incre]=v[i]; // flyttar incre steg till höger
				m_movements++;
				i -= incre;
			}
			v[i+incre]=temp;	// sätter in temp på korrekt plats i skalet
			m_movements++;
		}
		incre /= 2; // halverar incre
	}
}

///////////////////////////////////
// QUICK SORT
// T(n) = A*nlog(n)
///////////////////////////////////

template <class TYPE>
void CSort<TYPE>::quickSort(TYPE v[], int size)

{
	m_comparisions=0;
	m_movements=0;
	m_methodName="Quick sort";
	m_dataSize=size;
	rquickSort(v, 0, size-1, m_comparisions, m_movements);
}

template <class TYPE>
void CSort<TYPE>::heapSort(TYPE v[], int size)
{
	m_comparisions=0;
	m_movements=0;
	int i;

  for (i = (size / 2)-1; i >= 0; i--)
    shiftDown(v, i, size, m_comparisions,m_movements);

  for (i = size-1; i >= 1; i--)
  {
	swap(v[0],v[i]);
	m_movements+=3;
    shiftDown(v, 0, i-1, m_comparisions,m_movements);
  }
}

template <class TYPE>
void CSort<TYPE>::shiftDown(TYPE v[], int first, int last, int& comps, int& moves)
{
	int done, maxChild;
  done = 0;
  while ((first*2 <= last) && (!done))
  {
    if (first*2 == last)
      maxChild = first * 2;
    else if (comps++,v[first * 2] > v[first * 2 + 1])
      maxChild = first * 2;
    else
      maxChild = first * 2 + 1;
	  

    if (comps++,v[first] < v[maxChild])
    {
	  swap(v[first],v[maxChild]);
	  m_movements+=3;
      first = maxChild;
    }
    else
      done = 1;
  }
}


template <class TYPE>
void CSort<TYPE>::rquickSort(TYPE v[], int first, int last, int& comps, int& moves)
{
	if ((last-first) > m_quickSortMinSize)
	{
		medianLeft(v,first, last, comps, moves);
		TYPE pivot=v[first];
		moves++;
		int sortLeft=first+1;
		
		int sortRight=last;
		
		while (sortLeft <= sortRight)
		{
			while (comps++,v[sortLeft]<pivot)
				sortLeft++;
			while (comps++,v[sortRight]>=pivot)
				sortRight--;
			
			if (sortLeft<=sortRight)
			{
				TYPE temp=v[sortLeft];
				v[sortLeft]=v[sortRight];
				v[sortRight]=temp;
				moves+=3;
				sortLeft++;
				sortRight--;
			}
		}

		v[first]=v[sortLeft-1];
		v[sortLeft-1]=pivot;
		moves+=2;

		if (first < sortRight)
			rquickSort(v, first, sortRight-1, comps, moves);
		if (sortLeft<last)
			rquickSort(v, sortLeft, last, comps, moves);
	}
	else
		quickInsertionSort(v, first, last, comps, moves);
}

template <class TYPE>
void CSort<TYPE>::medianLeft(TYPE v[], int left, int right, int& comps, int& moves)
{
	int mid=(left+right)/2;
	TYPE temp;

	if (comps++,v[left]>v[mid])
	{
		temp=v[left];
		v[left]=v[mid];
		v[mid]=temp;
		moves+=3;
	}

	if (comps++,v[left]>v[right])
	{
		temp=v[left];
		v[left]=v[right];
		v[right]=temp;
		moves+=3;
	}
	
	if (comps++,v[mid]>v[right])
	{
		temp=v[mid];
		v[mid]=v[right];
		v[right]=temp;
		moves+=3;
	}

	temp=v[left];
	v[left]=v[mid];
	v[mid]=temp;
	moves+=3;
}

template <class TYPE>
void CSort<TYPE>::quickInsertionSort(TYPE v[], int first, int last, int& comps, int& moves)
{
	int i;
	TYPE temp;
	int current;

	for (current=first+1; current<=last; current++)
	{
		temp=v[current];
		moves++;
		i=current-1;
		while (comps++,i>=0 && temp<v[i])
		{
			v[i+1]=v[i];
			moves++;
			i--;
		}
		v[i+1]=temp;
		moves++;
	}
}





///////////////////////////////////////
// Funktion som visar information
// om senaste utförda sortering
///////////////////////////////////////

template <class TYPE>
void CSort<TYPE>::display() const
{
	cout << "Method       : " << m_methodName << endl;
	cout << "Data size    : " << m_dataSize << endl;
	cout << "Comparisions : " << m_comparisions << endl;
	cout << "Movements    : " << m_movements << endl;		
}