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
