fundamental.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 InsertionSort(vector<int> &);

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

int BubbleSort(vector<int> &);

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

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

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

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

void sort::fundamental(vector<int> & vec, int size, int k, vector<int> & vec_temp)
{

	std::vector<int> vecIS(vec);//inputfor Insertion sort
	std::vector<int> vecMS(vec);//input for merge sort
	std::vector<int> vecIMS(vec);//input for insertion-merge-sort
	std::vector<int> vecBS(vec);//input for bubble sort
	std::vector<int> vecQS(vec);//input for quick sort
	std::vector<int> vecSS(vec);//input for selection sort
	std::vector<int> vecCS(vec);//input for counting sort
	std::vector<int> vecforout(size);//for counting sort
	
	std::ostream_iterator<int> output(cout, "	" );
	int max, min;

/*	cout<<"The number of comparison performed by InsertionSort is "<<InsertionSort(vecIS)<<endl;
	cout<<"The number of comparison performed by BubbleSort is "<<BubbleSort(vecBS)<<endl;
	cout<<"The number of comparison performed by MergeSort is "<<MergeSort(vecMS,0,size)<<endl;
	cout<<"The number of comparison performed by Insertion-Merge-Sort is "<<Insertion_on_Merge_Sort(vecIMS,0,size-1,k)<<endl;
	cout<<"The number of comparison performed by QuickSort is "<<QuickSort(vecQS,0,size-1)<<endl;
	cout<<"The number of comparison performed by SelectionSort is "<<SelectionSort(vecSS,size)<<endl;

	cout<<"The number of assignments performed by CountingSort is "<<CountingSort(vecCS,vecforout,size,max,min)<<endl;
	cout<<"The maximum number in the array is " <<max<<endl;
	cout<<"The minimum number in the array is " <<min<<endl;
*/	
	vec_temp.at(0)+=InsertionSort(vecIS);
	vec_temp.at(1)+=BubbleSort(vecBS);
	vec_temp.at(2)+=MergeSort(vecMS,0,size);
	vec_temp.at(3)+=Insertion_on_Merge_Sort(vecIMS,0,size-1,k);
	vec_temp.at(4)+=QuickSort(vecQS,0,size-1);
	vec_temp.at(5)+=SelectionSort(vecSS,size);
	vec_temp.at(6)+=CountingSort(vecCS,vecforout,size,max,min);

	//return 0;
    
}


int InsertionSort(vector<int> & v){
	int i,j,temp;
	int countnum=0; 
	for(j=1; j<v.size(); j++){
		i=j-1;
		temp=v.at(j);
		for(;i>=0 && v.at(i)>temp;i--){
				countnum++;       //sum the comparison steps
				v.at(i+1)=v.at(i);
		}
		if(i!=-1){         // when i is not -1 
			countnum++;    // it is the reason that v.at(i)<=temp leads to jump out of comparision loop
		}                  // so countnum need add 1
		v.at(i+1)=temp;
	} 
	return countnum;
}



int MergeSort(vector<int> & v, int p, int r)
{
	int countnum=0;
    if(p+1<r){
        int q=(p+r)/2;
        countnum+=MergeSort(v,p,q);//sum the comparison steps
        countnum+=MergeSort(v,q,r);//sum the comparison steps
        countnum+=Merge(v,p,q,r);//sum the comparison steps
    }
	return countnum;
}	

int Merge(vector<int> & v , int p, int q, int r)
{
    int i=p;
    int j=q;
	int countnum=0;
	std::vector< int > merger;//set a storage vector
//find the smaller one from the two number which obtained from the two parts of the vector v respectively//
    while( (i < q) && (j < r) )
	{
		countnum++;//sum the comparison steps
        if(v.at(i)>=v.at(j)){//find the smaller one
            merger.push_back(v.at(j));//add the smaller one
            j++;
        }
		else
		{
           merger.push_back(v.at(i));
           i++; 
        }
    }
//////////////////////////////////////////////////////////////////////////////////////////////////////////
	while(j<r){//add the numbers left in q to r part of v into merger
		countnum++;//sum the comparison steps
        merger.push_back(v.at(j));
        j++;
    }
	
    while(i<q){//add the numbers left in p to q part of v into merger
		countnum++;//sum the comparison steps
        merger.push_back(v.at(i));
        i++;
    }
	
	i=p;
	int k;
    for(k=0;k<merger.size();k++){//copy the sorted vector back to vector v
		v.at(i)=merger.at(k);//copy the sorted vector back to vector v
		i++;//copy the sorted vector back to vector v
	}
	return countnum;//return the comparison number
}

int Insertion_on_Merge_Sort(vector<int> & v, int p, int r, int k){
	int countnum=0;
	if(r-p+1<=k)
		countnum+=InsertionSort(v);//sum the comparison steps
	else{
        int q=(p+r)/2;
        countnum+=MergeSort(v,p,q);//sum the comparison steps
        countnum+=MergeSort(v,q,r);//sum the comparison steps
        countnum+=Merge(v,p,q,r);//sum the comparison steps
    }
	return countnum;
}



int BubbleSort(vector<int> & v){
	int i,j,temp;
	int countnum=0;
	int n=v.size();
	for(i=0; i<n; i++){
		for(j=n-1; j>i; j--){
			countnum++;           //sum the comparison steps
			if(v.at(j)<v.at(j-1)){
				temp=v.at(j);
			    v.at(j)=v.at(j-1);
				v.at(j-1)=temp;
			}
		}
	}
	return countnum;
}



int QuickSort(vector<int> & v, int p, int r){
	int q;
	int countnum=0;
	if(p<r){
		q=Partition(v,p,r, countnum);
		countnum+=QuickSort(v,p,q-1);//sum the comparison steps
		countnum+=QuickSort(v,q+1,r);//sum the comparison steps
	}
	return countnum;
}

int Partition(vector<int> & v, int  p, int r, int& countnum){
	int x,i,j,temp;
	x=v.at(r);
	i=p-1;
	for(j=p;j<r;j++){
		countnum++;         //sum the comparison steps
		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;
}


int CountingSort(vector<int> &a, vector<int> &b, int size, int& max, int& min){
	min=a.at(0);//initial the minimum value
	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 countnum=0;

	int* counts= new int[distance];
	for (i = 0; i < distance; ++i) 
		counts[i] = 0;
	for (i = 0; i < size; ++i){
		countnum++;                    //sum the assignment steps
        ++counts[ a.at(i) - min ];
	}
	for (i = 1; i < distance; ++i){
		counts[i] += counts[ i - 1 ];
		countnum++;                    //sum the assignment steps
	}
	for (i = size - 1; i >= 0; --i){
		countnum=countnum+2;           //sum the assignment steps
		b.at(--counts[ a.at(i) - min ])=a.at(i);//store the sorted number to output vector
	}
				
    delete[] counts; //release the array counts
	return countnum;

}



int SelectionSort(vector<int> & v, int size){
	int min,temp;
	int countnum=0;
	for(int i=0;i<size-1;i++){
		min=i;
		for(int j=i+1; j<size; j++){
			countnum++;                   //sum the comparison steps
			if(v.at(j)<v.at(min)){        //find the position of ith smallest number
				min=j;
			}
		}
		temp=v.at(i);      //exchange value v(i) with the ith smallest number
		v.at(i)=v.at(min);
		v.at(min)=temp;
	}
	return countnum;
}