Untitled

Sort.h#pragma oncetemplate <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 templatentemplate 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;		}