Execute these using C++ language. You are to do the following: 4. Modify the bub
ID: 3687989 • Letter: E
Question
Execute these using C++ language.
You are to do the following:
4. Modify the bubble-sort function such that the outer loop stops iterating as soon as there have been no swaps in the inner loop. That is, as soon as the array is already sorted.
5. Modify each function such that you count the number of comparisons between array elements that they perform. Each function will output the final sorted array and the number of comparisons the function has performed.
In each of the following questions you are given two functions A and B.
You need to find an array for each case such that function A outperforms function B (i.e. number of comparisons function A performs / number of comparisons function B performs is minimized: the smaller this number higher your score).
You may write a separate C++ program (or program segment, or function) for each case. Make sure that THE ORGINAL ARRAY YOU FIND (INPUT) (this input is to be hard-coded in your submission), the final sorted array, number of comparisons, and ratio of number of comparisons are printed for each case.
Note that to be able to answer this question you should understand how each algorithm works, and works best on what kind of input, while other alternate algorithms do not perform similarly well (perform much worse as much as possible).
a) A=Selection Sort, B=Insertion Sort
b) A=Selection Sort, B=Modified Bubble Sort
c) A=Insertion Sort, B=Selection Sort
d) A=Insertion Sort, B=Modified Bubble Sort
e) A=Modified Bubble Sort, B=Insertion Sort
f) A=Modified Bubble Sort, B=Selection Sort
Selection Sort:
void selection(int a[], int l, int r)
{ for (int i = l; i < r; i++)
{ int min = i;
for (int j = i+1; j <= r; j++)
if (a[j] < a[min]) min = j;
exch(a[i], a[min]);
} }
Insertion Sort:
void insertion(int a[], int l, int r)
{ int i; for (i = r; i > l; i--) compexch(a[i-1], a[i]);
for (i = l+2; i <= r; i++)
{ int j = i; int v = a[i];
while (v < a[j-1])
{ a[j] = a[j-1]; j--; }
a[j] = v; }
}
Bubble Sort:
void bubble(int a[], int l, int r)
{ for (int i = l; i < r; i++)
for (int j = r; j > i; j--) compexch(a[j-1], a[j]);
}
Explanation / Answer
4.Modified Bubble Sort
void bubble_sort(int a[] ,int size)
{
int i,j,k,temp,flag=1;
i=0;
while(i<size-1&& flag==1)
{
flag=0;
for(j=0;j<size-i-1;j++)
{
if(a[j]>a[j+1])
{
flag=1;
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
}
i++;
}
for(k=0;k<size;k++)
{
cout<<a[k];
}
cout<<"No. of passes :"<<i;
}
5.Modified selection sort and insertion sort
void selection_sort(int a[],int size)
{
int i,j,k,small,pos,count=0;
for(i=0;i<(size-1);i++)
{
small=a[i];
pos=i;
for(j=i+1;j<size;j++)
{
if(a[j]<small)
{
small=a[j];
pos=j;
}
}
a[pos]=a[i];
a[i]=small;
for(k=0;k<size;k++)
{
cout<<a[k];
}
}.
cout<<"No of passes"<<i;
}
void insertion_sort(int a[],int size)
{
int i,j,k,temp,count=0;
for(i=1;i<size;i++)
{
temp=a[i];
j=i-1;
if(temp<a[j])
{
while(temp<a[j]&&j>=0)
{
a[j+1]=a[j];
j--;
}
}
a[j+1]=temp;
for(k=0;k<size;k++)
{
cout<<a[k];
}}
cout<<"No.of passes:"<<i-1;
}
a) A=Selection Sort, B=Insertion Sort
void main()
{
int a[],size,i ,m,n;
cout<<"Enter the array elements";
for(i=0;i<size;i++)
{
cin>>a[i];
}
int insertion_sort(a[],size);//prototype
int selection_sort(a[],size);//prototype
m=insertion_sort(a[],size);
n=selection_sort(a[],size);
int r=m/n;
cout<<"The ratio of number of comparisons"<<r;
return 0;
}
int selection_sort(int a[],int size)
{
int i,j,k,small,pos,count=0;
for(i=0;i<(size-1);i++)
{
small=a[i];
pos=i;
for(j=i+1;j<size;j++)
{
if(a[j]<small)
{
small=a[j];
pos=j;
}
}
a[pos]=a[i];
a[i]=small;
cout<<"The final result after selection sort is:";
for(k=0;k<size;k++)
{
cout<<a[k];
}
}.
return(i);
}
int insertion_sort(int a[],int size)
{
int i,j,k,temp,count=0;
for(i=1;i<size;i++)
{
temp=a[i];
j=i-1;
if(temp<a[j])
{
while(temp<a[j]&&j>=0)
{
a[j+1]=a[j];
j--;
}
}
a[j+1]=temp;
cout<<"The final result after insertion sort is:";
for(k=0;k<size;k++)
{
cout<<a[k];
}}
return(i-1);
}
The output will be:
enter the array elements:
35
20
4
10
5
The final result after insertion sort is:
4
5
10
20
35
The final result after selection sortis:
4
5
10
20
35
the ratio of the comparisons will be
4/4
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.