execution_time.cpp

各种排序方法的比较

#include <iostream>
#include <iterator>
#include <iomanip>
#include <vector>  
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#include "sort.h"

using namespace std;
using std::cout;
using std::cin;
using std::endl;

void InsertionSort(vector<int> &);

void MergeSort( vector<int> & , int, int);
void Merge( vector<int> & , int, int, int);

void BubbleSort(vector<int> &);

void QuickSort(vector<int> &, int, int);
int Partition(vector<int> &, int, int);

void CountingSort(vector<int> &, vector<int> &, int);
void CountingSort(vector<int> &, vector<int> &, int, double &);

void SelectionSort(vector<int> &, int);

void Insertion_on_Merge_Sort(vector<int> &, int, int, int);

void sort::execution_time(vector<int> & vec, int size, int k, vector<double> & vec_temp)
{
/////////////////////////////////copy the input vector for each algorithm's input vector/////////////////////////////////////
////////////////////Because each algorithm will change its input vector, can't be used by other algorithm////////////////////
	std::vector<int> vecIS(vec);//for Insertion sort
	std::vector<int> vecMS(vec);//for merge sort
	std::vector<int> vecIMS(vec);//for insertion merge sort
	std::vector<int> vecBS(vec);//for bubble sort
	std::vector<int> vecQS(vec);//for quick sort
	std::vector<int> vecSS(vec);//for selection sort
	std::vector<int> vecCS(vec);//for counting sort
	std::vector<int> vecCS_1(vec);//for counting sort
	std::vector<int> vecforout(size);//for counting sort
	std::vector<int> vecforout_1(size);//for counting sort
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//	std::ostream_iterator<int> output(cout, "	" );
/////////////////////////////////////////////////compute execution time for each algorithm/////////////////////////////////
	clock_t start,end; //set the start and finish mark
	double dif; // to store the cost time
	start=clock(); //record the start clock tick number
	InsertionSort(vecIS); 
	end=clock();//record the end clock tick number
	dif=difftime(end,start)/CLOCKS_PER_SEC;//compute the cost time
	vec_temp.at(0)+=dif;//compute the sum of execution time
//	cout<<"The processor time needed by InsertionSort is "<<dif<<endl;
	

	start=clock();//record the start clock tick number
	BubbleSort(vecBS);
	end=clock();//record the end clock tick number
	dif=difftime(end,start)/CLOCKS_PER_SEC;//compute the cost time
//	cout<<"The processor time needed by BubbleSort is "<<dif<<endl;
	vec_temp.at(1)+=dif;//compute the sum of execution time

	start=clock();
	MergeSort(vecMS,0,size);
	end=clock();
	dif=difftime(end,start)/CLOCKS_PER_SEC;
//	cout<<"The processor time needed by MergeSort is "<<dif<<endl;
	vec_temp.at(2)+=dif;

	start=clock();
	Insertion_on_Merge_Sort(vecIMS,0,size-1,k);
	end=clock();
	dif=difftime(end,start)/CLOCKS_PER_SEC;
//	cout<<"The processor time needed by Insertion_on_Merge_Sort is "<<dif<<endl;
	vec_temp.at(3)+=dif;
	
	start=clock();
	QuickSort(vecQS,0,size-1);
	end=clock();
	dif=difftime(end,start)/CLOCKS_PER_SEC;
//	cout<<"The processor time needed by QuickSort is "<<dif<<endl;
	vec_temp.at(4)+=dif;
	
	start=clock();
	SelectionSort(vecSS,size);
	end=clock();
	dif=difftime(end,start)/CLOCKS_PER_SEC;
//	cout<<"The processor time needed by SelectionSort is "<<dif<<endl;
    vec_temp.at(5)+=dif;

//	start=clock();
//	CountingSort(vecCS,vecforout,size);
//	end=clock();
//	dif=difftime(end,start)*1000/CLOCKS_PER_SEC;
//	cout<<"The processor time needed by CountingSort is "<<dif<<endl;
//	vec_temp.at(6)+=dif;

	CountingSort(vecCS_1,vecforout_1, size, dif);//just compute the execution of assignment part
	vec_temp.at(6)+=dif;//compute the sum of execution time
	
}


void InsertionSort(vector<int> & v){
	int i,j,temp;
	for(j=1; j<v.size(); j++){
		i=j-1;
		temp=v.at(j);
		for(;i>=0 && v.at(i)>temp;i--){
			v.at(i+1)=v.at(i); 
		}
		v.at(i+1)=temp;
	} 
}



void MergeSort(vector<int> & v, int p, int r)
{
    if(p+1<r){
        int q=(p+r)/2;
        MergeSort(v,p,q);
        MergeSort(v,q,r);
        Merge(v,p,q,r);
    }
}	

void Merge(vector<int> & v , int p, int q, int r)
{
    int i=p;
    int j=q;
	std::vector< int > merger;

    while( (i < q) && (j < r) )
	{
        if(v.at(i)>=v.at(j)){
            merger.push_back(v.at(j));
            j++;
        }
		else
		{
           merger.push_back(v.at(i));
           i++; 
        }
    }
	while(j<r){
        merger.push_back(v.at(j));
        j++;
    }
    while(i<q){
        merger.push_back(v.at(i));
        i++;
    }
	i=p;
	int k;

    for(k=0;k<merger.size();k++){
		v.at(i)=merger.at(k);
		i++;
	}
}

void Insertion_on_Merge_Sort(vector<int> & v, int p, int r, int k){
	if(r-p+1<=k)
		InsertionSort(v);
	else{
        int q=(p+r)/2;
        MergeSort(v,p,q);
        MergeSort(v,q,r);
        Merge(v,p,q,r);
    }
}



void BubbleSort(vector<int> & v){
	int i,j,temp;
	int n=v.size();
	for(i=0; i<n; i++){
		for(j=n-1; j>i; j--){
			if(v.at(j)<v.at(j-1)){
				temp=v.at(j);
			    v.at(j)=v.at(j-1);
				v.at(j-1)=temp;
			}
		}
	}
}



void QuickSort(vector<int> & v, int p, int r){
	int q;
	if(p<r){
		q=Partition(v,p,r);
		QuickSort(v,p,q-1);
		QuickSort(v,q+1,r);
	}
}

int Partition(vector<int> & v, int  p, int r){
	int x,i,j,temp;
	x=v.at(r);
	i=p-1;
	for(j=p;j<r;j++){
		if(v.at(j)<=x){
			i++;
			temp=v.at(i);
			v.at(i)=v.at(j);
			v.at(j)=temp;
		}
	}
	temp=v.at(i+1);
	v.at(i+1)=v.at(r);
	v.at(r)=temp;
	return i+1;
}


void CountingSort(vector<int> &a, vector<int> &b, int size){
	int min=a.at(0);
	int max=min;
	int i;
	for(i=1; i<size; i++){
		if(a.at(i)<min)
			min=a.at(i);
		else if(a.at(i)>max)
			max=a.at(i);
	}
	int distance=max-min+1;
    
	int* counts= new int[distance];
	for (i = 0; i < distance; ++i) 
                counts[i] = 0;
	for (i = 0; i < size; ++i)
                ++counts[ a.at(i) - min ];
	for (i = 1; i < distance; ++i)
                counts[i] += counts[ i - 1 ];
	for (i = size - 1; i >= 0; --i)
                b.at(--counts[ a.at(i) - min ])=a.at(i);
				
    delete[] counts;

}

void CountingSort(vector<int> &a, vector<int> &b, int size, double & dif){
	int min=a.at(0);//initial the minimum value
	int max=min;//initial the maximum value
	int i;
/////////////compute the distance between the minimum value and the maximum value//////////////
	for(i=1; i<size; i++){
		if(a.at(i)<min)
			min=a.at(i);
		else if(a.at(i)>max)
			max=a.at(i);
	}
	int distance=max-min+1;
//////////////////////////////////////////////////////////////////////////////////////////////   
	int* counts= new int[distance];//set a new array for storage

	clock_t start, end;//set the start and finish mark
	start=clock(); //record the start clock tick number
//////////////////////////////assignment part///////////////////////////////////////////////////////////////	

	for (i = 0; i < distance; ++i)//initial counts wiht 0 
                counts[i] = 0;
	for (i = 0; i < size; ++i)//compute the number of each value
                ++counts[ a.at(i) - min ];
	for (i = 1; i < distance; ++i)//compute the initial position of each value in output vector
                counts[i] += counts[ i - 1 ];
	for (i = size - 1; i >= 0; --i)//store the sorted number to output vector
                b.at(--counts[ a.at(i) - min ])=a.at(i);

	end=clock();//record the finish clock tick number
	dif=difftime(end,start)*1000/CLOCKS_PER_SEC;//compute the cost time
    delete[] counts; //release the array counts

}

void SelectionSort(vector<int> & v, int size){
	int min,temp;
	for(int i=0;i<size-1;i++){
		min=i;
		for(int j=i+1; j<size; j++){
			if(v.at(j)<v.at(min))
				min=j;
		}
		temp=v.at(i);
		v.at(i)=v.at(min);
		v.at(min)=temp;
	}
}