compare, datamove counter & timemeasurement for bubble,selection and insertion sort

[avillachandok]

hi,
Here is my code on the three sorts. I've place in the counter called icompare&imove for insertion sort; bcompare&bmove for bubble sort and scomare and smove for selection sort. I've also used time_t as a timer to calculate the time it takes to sort the three. can someone please help me out so I know i'm placing them in the right positions. i think my comparison counter is fine but i think my datamove counters are definetely wrong. really really need help. thanks.

//BUBBLE SORT
	int bcompare=0, bmove=0;
time_t bstart,bend;
//function performs bubble sort on a deque in ascending order
void bubbleSort(deque<string> &list, int N)
{
	time(&bstart);
	for(int i=1; i<N; i++)
	{
		for(int j=0; j<N-i; j++)
		{
			bcompare+=1;//data independent. it compares two values as it enter the two for loops
			if(list[j]>list[j+1])
			{
				exch(list[j],list[j+1]);
				bmove+=1;//data moves as it swap two values
			}
		}
	}
	time(&bend);
}
//SELECTION SORT
int scompare=0, smove=0;
time_t sstart,send;
//function peforms selection sort on a list in ascending order and the list
template<class T>
list<T> selectionSort (list<T> list, int N)
{
	typename std::list<T> original,temp,result;
	original = list;
	int tempsize;
	T smallest;//smallest value
	time(&sstart);
	do
	{
		smallest = original.front();//assumes first element is the smallest
		original.pop_front();
		while(!original.empty())
		{
			scompare+=1;
			if(original.front()<smallest)
			{
				temp.push_back(smallest);
				smallest = original.front();
				original.pop_front();
				smove+=1;
			}
			else
			{
				temp.push_back(original.front());
				original.pop_front();
			}
		}
		result.push_back(smallest);
		tempsize = temp.size();
		while(!temp.empty())
		{
			original.push_back(temp.front());
			temp.pop_front();
		}
	}while (tempsize!=0);//the do while loop
	time(&send);
	return result;
}
//INSERTION SORT
time_t istart, iend;
int icompare=0,imove=0;
//function performs insertion sort on a vector in ascending order
template<class T>
void insertionSort(vector<T> &list, int N)
{
	time(&istart);
	{
		for(int i=1;i<N;i++)
		{
			T temp = list[i];
			int j = i;
			while(j>0 && temp<list[j-1])
			{
				icompare+=1;//when while is true
				list[j] = list[j-1];
				imove+=1;//data assignment in while loop
				j--;
			}
				icompare+=1;//when while is false
			list[j] = temp;
			imove+=1;//data assignment at the end of comparisons
		}
	}
	time(&iend);
}//end insertion sort

ANY HELP WOULD BE APPRECIATED.

[StuXYZ]

well you seem to under count a little bit.

I personnally like to consider all comparisons. For example: while(j>0 && temp<list[j-1]) That is definately 2 comparisons.
And for(int i=1;i<N;i++) is definately one each time.

Effectively you have under counted a lot of times. BUT note that if you fill this in correctly then you will have a worst case senario since there a several cases were an optimizer will reduce the comparisons.

You also have to be careful about correctly adding extra counts. For example the for loop has N comparisons but is run N-1 times. The while loop has an extra 1 / 2 comparison.