hi,
i've an insertion sort algorithm and a selection sort algorithm.
i'm not sure how to measure the performace(best case and worst case in terms of N= size of the list, deque, vector etc.)
i'm trying to insert comparecount and movecount in the program.
Bubble sort was easy but im not sure how to do it for these two. and how to get the performance in term of N.

template<class T>
void insertionSort(vector<T> &list,int l, int r)
{
	for(int i=l+1;i<r;i++)
	{
		T temp = list[i];
		imovecount++;
		int j = i;
		while(j>l && (temp<list[j-1]))
		{
			icomparecount++;
			imovecount++;
			list[j] = list[j-1];
			j--;
		}
		icomparecount++;
		list[j] = temp;
		imovecount++;

	}
}

//function peforms selection sort on a list in ascending order and the list
	template<class T> list<T> selectionSort (list<T> list)
	{
		typename std::list<T> original,temp,result;//original is the list called. temp holds intermediate values. result holds sorted values
		original = list;
		int tempsize;
		T smallest;//holds the smallest <T> value
		do
		{
			smallest = original.front();//puts first element into smallest
			original.pop_front();//throws away the first element in the list
			while(!original.empty())//repeat until original is empty
			{
				if(less(original.front(),smallest))//If first element on list is less than smallest
				{
					temp.push_back(smallest);// Put smallest on temp
					smallest = original.front();//Put first element of list in smallest
					original.pop_front();
				}
				else
				{
					temp.push_back(original.front());//else put first element in list on temp
					original.pop_front();
				}
			}
			result.push_back(smallest);//When original list is empty put smallest on result
			tempsize = temp.size();
			while(!temp.empty())
			{
				original.push_back(temp.front());// Move all elements on temp back to original
				temp.pop_front();
			}
		}while (tempsize!=0);//Repeat process, until there are no elements to put back on original
		return result;//return the sorted list
	}

can someone please help me in where to insert the compare and the move for this selection sort. the programs run fine.
thanks,
arti

hi,
comparecount is an integer counter that I want to put inside the program so whenever the program compares two values of the list I increment the counter.
In the same manner i'm also trying to insert a movecount counter that is incremented by the no of times the program moves the values inside the list.
i have done this for the insertion sort and wanted to check if its right.
i also need to insert two counters in my selection sort so it can do the same thing.
hope this makes sense.
basically i need to estimate the performance of these two algorithms and then also put these counters so i can get statistical values so then i can see the relation.
thanks,
arti villa

This article has been dead for over six months. Start a new discussion instead.