For the following c++ code, check the number of actual comparisons and movements
ID: 3552913 • Letter: F
Question
For the following c++ code, check the number of actual comparisons and movements and THEORETICAL (I think this is just what the time and space equations compute but im not sure) comparisons and movements. Correct me if i'm wrong and change the code to make it output correct info.
The code:
IMPORTANT, the following functions all send the data to this function:
else if(user_choice == 4)
//If the variable user_choice is equivalent to 4 do the following.
{
ordered = true;
cout << "Performing Insertion Sort on the current list." << endl;
InsertionSort();
cout << endl << endl;
cout << "Theoretical sort statistics: " << (.5)*(size*size)-(.5)*(size);
cout << " element comparisons, " << 3*((.5)*(size*size)-(.5)*(size));
cout << " element movements" << endl;
cout << "Actual sort statistics: " << actual_comparisons;
cout << " element comparisons, " << actual_movements;
cout << " element movements.";
cout << endl << endl;
cout << "Finishing Insertion Sort." << endl;
cout << endl;
Display_List();
Display_Menu();
}
else if(user_choice == 5)
//If the variable user_choice is equivalent to 5 do the following.
{
ordered = true;
cout << "Performing Selection Sort on the current list." << endl;
SelectionSort();
cout << endl << endl;
cout << "Theoretical sort statistics: " << (.5)*(size*size)-(.5)*(size);
cout << " element comparisons, " << 3*(size-1);
cout << " element movements" << endl;
cout << "Actual sort statistics: " << actual_comparisons;
cout << " element comparisons, " << actual_movements;
cout << " element movement.";
cout << endl << endl;
cout << "Finishing Selection Sort." << endl;
cout << endl;
Display_List();
Display_Menu();
}
else if(user_choice == 6)
//If the variable user_choice is equivalent to 6 do the following.
{
cout << "Performing Linear Search on the current list." << endl;
cout << endl;
Search_Info(user_choice);
cout << endl << endl;
cout << "Theoretical search statistics: " << size << " element ";
cout << "comparisons" << endl;
cout << "Actual search statistics: " << actual_comparisons;
cout << endl << endl;
cout << "Finishing Linear Search." << endl;
cout << endl;
Display_List();
Display_Menu();
}
else if(user_choice == 7)
//If the variable user_choice is equivalent to 7 do the following.
{
if(ordered==true)
{
cout << "Performing Binary Search on the current list." << endl;
cout << endl;
Search_Info(user_choice);
cout << endl << endl;
cout << "Theoretical search statistics: " << size+2 << " element ";
cout << "comparisons" << endl;
cout << "Actual search statistics: " << actual_comparisons;
cout << " element comparisons.";
cout << endl << endl;
cout << "Finishing Binary Search." << endl;
cout << endl;
Display_List();
Display_Menu();
}
else
{
cout << "Sorry, since the current list is not known to be ";
cout << "ordered, the Binary Search " << endl << "cannot be ";
cout << "performed at this time. Please sort the current list ";
cout << "first." << endl;
cout << endl;
Display_List();
Display_Menu();
}
}
else
;
4. void AList::InsertionSort()
{
bool done;
int j;
actual_comparisons=0;
actual_movements=0;
int temp=0;
for(int i=1;i<size;i++)
{
j=i;
done=false;
while((j>=1)&&(done!=true))
{
if(items[j]<items[j-1])
{
Swap(j,j-1);
j--;
temp++;
}
else
{
done=true;
}
actual_comparisons++;
actual_movements=temp;
}
}
}
5. void AList::SelectionSort()
{
int maxpos;
actual_comparisons=0;
actual_movements=0;
int temp=0;
for(int i=(size-1);i>0;i--)
{
maxpos=0;
for(int j=1;j<=i;j++)
{
if(items[j]>items[maxpos])
{
maxpos=j;
}
else
{
Swap(i,maxpos);
temp++;
}
actual_comparisons++;
actual_movements=temp;
}
}
}
6. void AList::LinearSearch(element target, bool&found, int&position)
{
found=false;
position=0;
actual_comparisons=0;
while((!found)&&(position<size))
{
if(target==items[position])
{
found=true;
}
else
{
position++;
}
actual_comparisons++;
}
}
7.void AList::BinarySearch(element target, bool&found, int&position)
{
int low;
int mid;
int high;
found=false;
low=0;
high=(size-1);
actual_comparisons=0;
int temp=0;
while((!found)&&(low<=high))
{
mid=(low + high)/2;
if(target==items[mid])
{
found=true;
position=mid;
}
else if(target<items[mid])
{
high=(mid-1);
}
else
{
low=(mid+1);
}
actual_comparisons++;
}
}
Explanation / Answer
void AList::InsertionSort()
{
bool done;
int j;
actual_comparisons=0;
actual_movements=0;
int temp=0;
for(int i=1;i<size;i++)
{
j=i;
done=false;
while((j>=1)&&(done!=true))
{
if(items[j]<items[j-1])
{
Swap(j,j-1);
j--;
actual_movements++;
}
else
{
done=true;
}
actual_comparisons++;
actual_movements=temp;
}
}
}
void AList::SelectionSort()
{
int maxpos;
actual_comparisons=0;
actual_movements=0;
int temp=0;
for(int i=(size-1);i>0;i--)
{
maxpos=0;
for(int j=1;j<=i;j++)
{
if(items[j]>items[maxpos])
{
maxpos=j;
}
actual_comparisons++;
}
Swap(i,maxpos);
actual_movements++;
}
}
your selection sort technique needed some changes i have done the same.. Please have a look.. and ask in case of doubt..
your search technique was fine... you are correctly measuring comparisons.. in your insertion sort also you have found out correctly.. but there was no use of temp in there.. i have just made that change..