博客

我自己放了comparison Counter 和 swap Counter，可是不确定是不是对的

请高手帮我看下，非常感谢

void quickSortFirst(int data[],int lo,int hi)
{ 
	int pivot,l,r,temp;
	l = lo; 
	r = hi; 
	pivot=data[lo];	// choose First element as pivot
	
	while(l<r)  
	{  
		while(data[l]<pivot) 
		{
			++l;
			compCounterFirst++;	   // comparison counter ++
		}
		 
		while(data[r]>pivot) 
		{
			--r;
			compCounterFirst++;	   // comparison counter ++
		}
		     
		if(l>=r) 
			break;  
		
		temp = data[l];  
		data[l] = data[r];  
		data[r] = temp; 
		
		swapCounterFirst++;	   	   // swap counter ++
		 
		++l;  
		--r;  
	} 

	if(l==r) 
		l++; 

	if(lo<r) 
		quickSortFirst(data,lo,l-1); 
	if(l<hi) 
		quickSortFirst(data,r+1,hi); 
}

以下是完整代码我的程序的

#include <iostream>
#include <fstream>
#include <sstream>
#include <string>
#include <cstring>
#include <ctime>
using namespace std;

const int MAX=100000;

static int swapCounterFirst=0;
static int compCounterFirst=0;

static int swapCounterMedian=0;
static int compCounterMedian=0;

void intiArr (string, int[], int&);

void printArr (int[], int, int);

void heap_sort(int [], int);

void quickSortFirst(int [], int, int);

void quickSortMedian(int [], int, int);

int main ()
{
	int size=0;
	
	int totalNumberOfSwap=0;
	int totalNumberOfComparison=0;
	// int oriArr[MAX];

	int oriArr[]={4, 2, 7, 8, 1, 9, 3, 6, 5};

	size=sizeof(oriArr)/sizeof(int);

	cout<<"The source array:"<<endl;

	cout<<"Total number of integers is "<<size<<endl;

	int printWay=1;
	int sortWay=1;

	cout<<"Please select layout of display (1 for line, 2 for space)"<<endl;
	// cin>>printWay;	// let user select layout of display

	printArr(oriArr, size, printWay);	// print array on screen

	cout<<"Please select algorithm to sort array:"<<endl
		<<"\t1. heap sort"<<endl
		<<"\t2. quick sort (using the first element of the list as pivot element)"<<endl
		<<"\t3. quick sort (using the median element of the list as pivot element)"<<endl
		<<"Pleae enter your option: ";

	cin>>sortWay;	// let user select algorithm to sort array

	if(sortWay==1)
	{
		cout<<"After heap sort:"<<endl;

		heap_sort(oriArr, size);	//	heap sort the array
	}
	else if(sortWay==2)
	{
		cout<<"After quick sort (using the first element as pivot element):"<<endl;

		// recursive quick sort array using the first element
		quickSortFirst(oriArr, 0, size-1);	  
		
		totalNumberOfSwap = swapCounterFirst;
		totalNumberOfComparison = compCounterFirst;	    
	}
	else if(sortWay==3)
	{
		cout<<"After quick sort (using the median element as pivot element):"<<endl;

		// quick sort array using the median element
		quickSortMedian(oriArr, 0, size-1);
		
		totalNumberOfSwap = swapCounterMedian;
		totalNumberOfComparison = compCounterMedian;
	}
	else
	{
		cout<<"Your input is incorrect"<<endl;
	}

	printWay=2;

	printArr(oriArr, size, printWay);

	cout<<endl<<endl<<"Total number of integers = "<<size<<endl
		<<"Total Number Of Swap = "<<totalNumberOfSwap<<endl
		<<"Total Number Of Comparison = "<<totalNumberOfComparison<<endl;
	
	return 0;
}

void printArr (int a[], int size, int printWay)
{
	if(printWay == 1)
	{
		for(int i=0; i<size; i++)
		{
			cout<<a[i]<<endl;
		}
	}
	else if(printWay == 2)
	{
		for(int i=0; i<size; i++)
		{
			if(i!=0 && i%10==0)
				cout<<endl;

			cout<<a[i]<<"\t";
		}
	}
	else
	{
		cout<<"Your input is incorrect"<<endl;
	}
}


// ------------------- quick sort use FIRST element as pivot-------------------
void quickSortFirst(int data[],int lo,int hi)
{ 
	int pivot,l,r,temp;
	l = lo; 
	r = hi; 
	pivot=data[lo];	// choose First element as pivot
	
	while(l<r)  
	{  
		while(data[l]<pivot) 
		{
			++l;
			compCounterFirst++;	   // comparison counter ++
		}
		 
		while(data[r]>pivot) 
		{
			--r;
			compCounterFirst++;	   // comparison counter ++
		}
		     
		if(l>=r) 
			break;  
		
		temp = data[l];  
		data[l] = data[r];  
		data[r] = temp; 
		
		swapCounterFirst++;	   	   // swap counter ++
		 
		++l;  
		--r;  
	} 

	if(l==r) 
		l++; 

	if(lo<r) 
		quickSortFirst(data,lo,l-1); 
	if(l<hi) 
		quickSortFirst(data,r+1,hi); 
}
// ------------------- quick sort -------------------

// ------------------- quick sort use MEDIAN element as pivot-------------------
void quickSortMedian(int data[],int lo,int hi)
{ 
	int pivot,l,r,temp;
	l = lo; 
	r = hi; 
	pivot=data[(lo+hi)/2];	//	choose Median element as pivot
	
	while(l<r)  
	{  
		while(data[l]<pivot) 
		{
			++l;
			compCounterMedian++;	// comparison counter ++
		}
		 
		while(data[r]>pivot) 
		{
			--r;
			compCounterMedian++;	// comparison counter ++
		}
		     
		if(l>=r) 
			break;  
		
		temp = data[l];  
		data[l] = data[r];  
		data[r] = temp; 
		
		swapCounterMedian++;		// swap counter ++
		 
		++l;  
		--r;  
	} 

	if(l==r) 
		l++; 

	if(lo<r) 
		quickSortMedian(data,lo,l-1); 
	if(l<hi) 
		quickSortMedian(data,r+1,hi); 
}
// ------------------- quick sort -------------------


// ------------------- heap sort -------------------
void max_heapify(int data[],int i,int heapsize)
{
    int l=2*i+1;
    int r=2*i+2;
    int largest=i;
    if(l<heapsize&&data[l]>data[i])
    {
        largest=l;
    }
    if(r<heapsize&&data[r]>data[largest])
    {
        largest=r;
    }
    if(largest!=i)
    {
        int temp=data[largest];
        data[largest]=data[i];
        data[i]=temp;
        max_heapify(data,largest,heapsize);
    }
}

void bulid_max_heap(int data[],int heapsize)
{
    for(int i=heapsize/2-1;i>=0;i--)
         max_heapify(data,i,heapsize);
}

void heap_sort(int data[],int heapsize)
{
     bulid_max_heap(data,heapsize);
     for(int i=heapsize-1;i>0;i--)
     {
         int t=data[0];
         data[0]=data[i];
         data[i]=t;
         max_heapify(data,0,i);

     }
}
// ------------------- heap sort -------------------