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.

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.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.