main.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;

int main(){
	const int size=5000; //set array size
    const int k=50;		//set Insertion-Merge-Sort changing point
	const int num=50;	//set the number of arrays with same size need to be implement
	int i,j;

	std::vector<int> vec_temp1(7,0); //store the sum of fundamental operations
	std::vector<double> vec_temp2(7,0); //store the sum of processor time
	std::vector<int> average_fundamental_operation(7,0);// store the average fundamental operations
	std::vector<double> average_execution_time(7,0);//store the average execution time
	sort sort_a;//set a sort class variable 
///////////////////////////////////////////output the initial condition//////////////////////////////////
	cout<<"The size of the array need to be sorted is "<<size<<endl;
	cout<<"The length of subarray for Insertion-Merge-Sort is "<<k<<endl;
	cout<<"The number of trials for arrays with the same size is "<<num<<endl;
/////////////////////////////////////////////////////////////////////////////////////////////////////////

	for(j=0;j<num;j++){
//////////////////////////////////////////generate a random array////////////////////////////////////////
		int iArray[size];
		srand((unsigned)time(NULL));  
		for(i=0;i<size;i++){
            iArray[i]=rand(); // to generate a random number range from 0 to 32767
		}
/////////////////////////////////////////////////////////////////////////////////////////////////////////
		std::vector<int> vec(iArray, iArray+size); //copy the random array to the vector vec
	//	sort_a.fundamental(vec, size, k, vec_temp1);//compute the fundamental operation
		sort_a.execution_time(vec, size, k, vec_temp2);//compute the execution time
	
	}
////////////////////////compute and output the average value for each algorithm//////////////////////////
	for(i=0;i<7;i++){
	//	average_fundamental_operation.at(i)=vec_temp1.at(i)/num;
		average_execution_time.at(i)=vec_temp2.at(i)/(double)num;
	}
	
	cout<<"The average number of comparison performed by InsertionSort is "<<average_fundamental_operation.at(0)<<endl;
	cout<<"The average number of comparison performed by BubbleSort is "<<average_fundamental_operation.at(1)<<endl;
	cout<<"The average number of comparison performed by MergeSort is "<<average_fundamental_operation.at(2)<<endl;
	cout<<"The average number of comparison performed by Insertion-Merge-Sort is "<<average_fundamental_operation.at(3)<<endl;
	cout<<"The average number of comparison performed by QuickSort is "<<average_fundamental_operation.at(4)<<endl;
	cout<<"The average number of comparison performed by SelectionSort is "<<average_fundamental_operation.at(5)<<endl;
	cout<<"The average number of assignments performed by CountingSort is "<<average_fundamental_operation.at(6)<<endl;

	cout<<"The average execution time performed by InsertionSort is "<<average_execution_time.at(0)<<endl;
	cout<<"The average execution time performed by BubbleSort is "<<average_execution_time.at(1)<<endl;
	cout<<"The average execution time performed by MergeSort is "<<average_execution_time.at(2)<<endl;
	cout<<"The average execution time performed by Insertion-Merge-Sort is "<<average_execution_time.at(3)<<endl;
	cout<<"The average execution time performed by QuickSort is "<<average_execution_time.at(4)<<endl;
	cout<<"The average execution time performed by SelectionSort is "<<average_execution_time.at(5)<<endl;
	cout<<"The average execution time performed by CountingSort is "<<average_execution_time.at(6)<<endl;

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////	
	return 0;
}